Reconstructing Fan Movement Order

There are \(n\) city squares labeled from \(1\) to \(n\) and \(m\) one‐way streets among some of them. Initially, each square is occupied by a group of fans supporting different teams.

The \(n\) groups act in a certain order as follows:

• If a group’s home square is unoccupied when its turn comes, it occupies that square and initiates a depth-first search (DFS) to capture additional squares.
• From an occupied square \(u\), the group attempts to move along every outgoing edge \((u,v)\). If \(v\) is unoccupied, it is captured (and becomes part of the same DFS tree). Otherwise, if \(v\) has been captured by another group, a conflict occurs on edge \((u,v)\) and the group does not proceed in that direction.
• If a group’s own square has already been occupied by a previous group, it does nothing on its turn.

We are given the full list of one‐way streets and a designated subset of these edges on which conflicts occurred. In a valid simulation the following properties hold:

• For every non‐conflict edge \((u,v)\) (i.e. with \(t=0\)), when the DFS is attempted from \(u\) the square \(v\) must be unoccupied, so \(v\) will be captured as part of the DFS initiated by the leader (the group that first occupied its DFS tree).
• For every conflict edge \((u,v)\) (i.e. with \(t=1\)), it must be that \(v\) is the leader of its DFS tree and has already acted (occupied its square) before the DFS from \(u\) (or its tree) reached \(v\).

Your task is to output a permutation of \(\{1,2,...,n\}\) representing an order in which the groups act so that the simulation produces exactly the given set of conflict edges.

Formula Note: All formulas are to be written in LaTeX format, as shown above.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1\le n\le 10^5\), \(0\le m\le 10^5\)): the number of city squares and the number of one‐way streets.

Then follow \(m\) lines. Each line contains three integers \(u\), \(v\), and \(t\) where \(u\) and \(v\) indicate a one‐way street from \(u\) to \(v\). If \(t = 0\), then the edge is traversed without conflict (i.e. it is used in the DFS to capture \(v\)); if \(t = 1\), a conflict occurred on edge \((u,v)\). It is guaranteed that the input is consistent with some fan movement order.

outputFormat

Output a permutation of the integers from \(1\) to \(n\) (separated by spaces) representing the order in which the fan groups act.

sample

3 2
1 2 0
2 3 0

1 2 3