Fan Groups

A city has $n$ squares, numbered $1$ through $n$, connected by $m$ one-way streets. The city also has $n$ football fan groups; the headquarters of fan group $i$ sits on square $i$.

On a certain day the groups stage a "city tour": one by one, in a pre-agreed order, each group tries to take over squares. Initially no square is taken over. The groups act strictly one after another — a group begins its turn only after the previous group has finished.

When it is fan group $i$'s turn:

• If square $i$ has already been taken over by some other group $j \ne i$, group $i$ does nothing.
• Otherwise, group $i$ takes over square $i$ and then spreads out. Whenever the group takes over a square $v$, it sends fans along every street leaving $v$. For a street $v \to w$: if $w$ is already taken over by a different group, the group cannot pass and a fight breaks out in that street; if $w$ is not yet taken over, the group takes over $w$ as well and keeps spreading from there.
• The turn ends once no more free squares can be reached.

Because two groups meet exactly on the streets where a fight happens, the fights precisely record which streets were blocked. You are given the city map together with, for every street, whether a fight occurred in it. Reconstruct an order in which the groups could have acted.

The first line contains two integers $n$ and $m$ — the number of squares and one-way streets. Each of the next $m$ lines contains three integers $a$, $b$, and $c$, describing a one-way street from square $a$ to square $b$: $c = 1$ means a fight occurred in this street, and $c = 0$ means it did not. For any two distinct squares there is at most one street between them in each direction.

If no acting order produces fights in exactly the marked streets (and in no other street), print $-1$.

Otherwise print, on a single line, the lexicographically smallest valid order: a permutation $P_1\ P_2\ \dots\ P_n$ of the numbers $1$ through $n$, separated by single spaces. It means the group from square $P_1$ acted first, then the group from square $P_2$, and so on. Among all valid orders, output the lexicographically smallest sequence (compare $P_1$ first, then $P_2$, and so on).

• $2 \le n \le 20,000$
• $1 \le m \le 200,000$
• $1 \le a, b \le n$, $a \ne b$, $c \in {0, 1}$

Consider $8$ squares and $9$ one-way streets, with fights recorded in the streets $1 \to 4$, $1 \to 8$, $7 \to 4$, and $7 \to 1$. One valid acting order is $8, 5, 6, 2, 3, 1, 7, 4$:

• Group $8$ goes first and takes over square $8$.
• Group $5$ takes over squares $5$, $6$, and $4$ (all reachable through free squares).
• Group $6$ finds its square already taken and does nothing.
• Group $2$ takes over squares $2$ and $3$.
• Group $3$ does nothing.
• Group $1$ takes over square $1$; streets $1 \to 4$ and $1 \to 8$ lead to already-taken squares, so fights break out there.
• Group $7$ takes over square $7$; streets $7 \to 1$ and $7 \to 4$ lead to already-taken squares, so fights break out there.
• Group $4$ does nothing.

This order produces exactly the four recorded fights, so it is valid. This input has several valid orders (for example $2, 3, 8, 4, 1, 7, 5, 6$ works too); the required answer is the lexicographically smallest one, which is $2\ 3\ 4\ 5\ 6\ 8\ 1\ 7$. By contrast, the order $8, 5, 6, 3, 2, 1, 7, 4$ is invalid, because it would create a fight in street $2 \to 3$, which is not marked.