Junyi was playing with a link cut tree last night. He has made ~Q~ LCA queries to his link cut tree. Each time, the link cut tree responded with the integer representing the lowest common ancestor. He cut one too many edges and now he can't restore his tree. However, he will be satisfied with any tree that will give him the same results when asked the LCA queries again. Your task is to help him restore his tree. You will be given the ~Q~ queries, and the result of those queries.

Input Specification

On the first line, two integers, ~N~ and ~Q~ ~({1 \le N, Q \le 10^5})~ where ~N~ is the number of nodes.

On the next ~Q~ lines, three integers ~u_i~ ~v_i~ and ~w_i~, which indicates that the LCA of ~u_i~ and ~v_i~ is ~w_i~. ~({1 \le u_i, v_i, w_i \le N})~.

Output Specification

~N~ integers, indicating that the parent of ~i~ is ~p_i~. (e.g. if the first integer is ~2~, then the parent of ~1~ is ~2~, if the second integer is ~5~, then the parent of ~2~ is ~5~). Node ~1~ is always the root, and has special value ~0~ as the parent. In other words, ~{p_1 = 0}~.

Sample Input

4 3
1 2 1
2 3 2
3 4 3

Sample Output

0 1 2 3