题目描述

很久以前，有一个美丽的村落，村落由 $n$ 间房屋和 $m$ 条道路构成，每个房子连出的边都不会指向它自身。道路可能是单向的，也可能是双向的，两个房子之间不会有多条道路。如果从房屋 $a$ 仅走一条道路可以到达房屋 $b$，则称 $a\rightarrow b$。

这个村落的道路遵循着如下「唯美」的规律：

若 $a\rightarrow b$ 且 $a\rightarrow c$，则 $b,c$ 之间一定无道路，且如果 $d\rightarrow b$，那么，一定有 $d\rightarrow c$。

由此，这个村落就有了「唯美村落」之称，某一天，小 P 想从某个房屋出发，沿着道路拜访每个房屋恰一次，最后回到开始的房屋。小 P 知道这是经典的 Hamilton 回路问题，一般人在多项式时间内是解决不了的，但他相信你能解决。另外，小鹏提出了更高的要求，他给每个房屋定了一个重要值，各房屋的重要程度互不相同，他将把起点选在最重要的房屋上，然后尽量先访问重要值大的房屋，即要求依次访问的房屋的重要值组成的序列的字典序尽量大。

输入格式

第一行包含两个正整数 $n,m$。

第二行包含 $n$ 个用空格隔开整数，分别表示每个房屋的重要值。

接下来 $m$ 行，每行三个正整数 $a,b,c$，表示一条边，$c=1$ 代表 $a$ 连向 $b$，$c=2$ 代表这是一条双向边。

输出格式

如果原图不存在 Hamilton 回路，则输出 -1；否则输出 $n$ 行，为 $1\sim n$ 的一个排列，即最佳的 Hamilton 回路，排列的第一个数为起点，最后一个数实际上是连向起点的。

样例输入

5 7
50 40 30 20 10
1 3 2
1 4 2
2 3 1
2 4 1
3 5 1
4 5 1
5 2 1

样例输出

1
3
5
2
4

数据规模与约定

$30\%$ 的数据满足 $n\le 100$，$m\le 10^3$

$100\%$ 的数据满足 $3\le n\le 2\times 10^4$，$m\le 5\times 10^5$；题给的都是「唯美村落」。