题目描述

给定一个有向图，每个节点关联于一群人。这 $n$ 群人按照某个特定的顺序进行以下操作：

• 到达并占领他们关联的节点；
• 从他们占领的某个节点 $u$ 出发，走到与其相邻的每个点 $v$。如果点 $v$ 已经被人占领，他们会边 $(u,v)$ 上发生冲突，并不再在这个方向上前进；否则，他们会占领点 $v$，并重复这一步，直到没有能到达的点为止。
• 如果他们关联的节点在此前被别的人群占领，他们不会与那群人发生冲突。在这种情况下，他们什么都不做。

给定该图，以及发生冲突的边集。求一种人群的行动顺序，使得发生冲突的边集与输入相符。

以样例为例。关联于点 $8$ 的人群首先行动，占领点 $8$；接下来关联于点 $5$ 的人群行动，占领点 $4,5,6$ （与 $4$ 相连的点 集）；关联于点 $6$ 的人群出动，因为点 $6$ 已经被占领，他们什么都不做；人群 $2$ 占领点 $2,3$；人群 $3$ 什么都不做；人 群 $1$ 占领点 $1$，并在边 $<1,4>$ 和 $<1,8>$ 上引发冲突；人群 $7$ 占领点 $7$ 并在边 $<7,1>$ 和 $<7,4>$ 上引发冲突；人群 $4$ 什么都不做。

注意合法的顺序可能不止一种；样例中， $(2, 3, 8, 4, 1, 7, 5, 6)$ 也是一种合法的方案。注意 $(8, 5, 6, 3, 2, 1, 7, 4)$ 不是合法的方案，因为按照这个方案，$<2,3>$ 上也会发生冲突，与输入不符。

输入格式

输入的第一行包含两个整数 $n,m$，含义是点数和边数。

接下来 $m$ 行，每行三个整数 $A,B,C$，表示有向边 $A\to B$，如果 $C=1$，则这条边上发生了冲突。

输出格式

输出一个排列，表示人群的行动顺序。

如果没有任何顺序满足题意，输出-1。

样例输入

8 9
1 4 1
1 8 1
2 3 0
5 6 0
6 5 0
7 4 1
6 4 0
7 1 1
4 5 0

样例输出

8 5 6 2 3 1 7 4

数据规模与约定

对于 $100\%$ 的数据，$n\leq 2\times 10^4$，$m \leq 2\times 10^5$。

题目来源

Dragonite提供SPJ