Background

The BOI World Cup is about to start, and fan groups are promoting the teams they support in the city.

Problem Description

There are $n$ city squares (labeled from $1$ to $n$) and $m$ directed streets between some of them. Initially, there is one group of fans in each square (each group supports a different team).

These $n$ fan groups perform the following actions in some specific order:

• They occupy the square where they are located (for example, the group in square $1$ will first occupy square $1$).
• Starting from some occupied square $u$, they go to every adjacent square $v$. If square $v$ has already been occupied by someone else, they will have a conflict on edge $(u,v)$ and will not continue in that direction; otherwise, they will occupy square $v$ and repeat this step, until there are no more reachable squares.
• If their own starting square has already been occupied earlier by another group, they will not have a conflict with that group. In this case, they do nothing.

Given the city and the set of edges where conflicts occur, find an order of actions of the fan groups such that the set of conflict edges matches the input.

Input Format

The first line contains two integers $N,M$, representing the number of vertices and the number of edges.

The next $M$ lines each contain three integers $A_i,B_i,C_i$, representing a directed edge $A_i\rightarrow B_i$. If $C_i=1$, then a conflict occurs on this edge.

Output Format

Output one permutation, the action order of the fan groups.

If there is no valid solution, output -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

Hint

Special Judge is provided by TOBapNw. If the SPJ is incorrect, please contact them.

Constraints

Subtask#0 is the sample.

$3\le N\le 2\times10^4$, $M\le\min(\frac{N\times(N-1)}{2},2\times10^5)$, $1\le A_i,B_i\le N$, $C_i\in\{0,1\}$.

Sample Explanation

The fans in square $8$ act first and occupy square $8$.

Next, the fans in square $5$ act and occupy squares $4,5,6$.

Next, the fans in square $6$ act; since square $6$ has already been occupied, they do nothing.

Next, the fans in square $2$ occupy squares $2,3$.

The fans in square $3$ do nothing.

Next, the fans in square $1$ act, occupy square $1$, and cause conflicts on edges $(1,4),(1,8)$.

The fans in square $7$ occupy square $7$ and cause conflicts on edges $(7,1),(7,4)$.

Note that there may be more than one valid order. In the sample, $(2,3,8,4,1,7,5,6)$ is also a valid solution.

Note that $(8,5,6,3,2,1,7,4)$ is not a valid solution, because under this order, a conflict would also occur on $(2,3)$, which does not match the input.

Translated by ChatGPT 5