D. Colorful Paths
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph with $$$n$$$ nodes and $$$m$$$ edges. The color of the $$$i$$$-th edge is $$$c_i$$$.

We call a path (does not have to be a simple path) colorful iff it does not have two consecutive edges of the same color.

Find all nodes $$$x$$$ such that there exist a colorful path starting from $$$1$$$ and ending at $$$x$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le m \le 10^6$$$) — the number of nodes and the number of edges.

Next $$$m$$$ lines describe edges: $$$i$$$-th line contains three integers $$$u_i, v_i, c_i$$$ ($$$1 \le u_i, v_i, \le n$$$; $$$u_i \ne v_i$$$; $$$1 \le c_i \le m$$$) — defining the edge from $$$u_i$$$ to $$$v_i$$$ of color $$$c_i$$$.

The sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output all the nodes $$$x$$$ such that there exist a colorful path starting from $$$1$$$ and ending at $$$x$$$ in ascending order.

Example
Input
4
5 6
1 2 1
2 3 1
2 4 2
4 2 3
3 4 3
3 5 1
3 2
1 3 1
2 1 1
5 5
1 2 1
2 3 2
3 4 3
4 2 2
2 5 1
1 0
Output
1 2 3 4 
1 3 
1 2 3 4 5 
1