You are given an undirected graph that has ~n~ vertices and ~m~ edges. You should output the list of edges in lexicographic order. Note that if there is more than one edge between two vertices, you should output the smallest weight edge only.

Input

• The first line contains two integers ~n, m~ ~(0 < n, m ≤ 10^5)~.
• Each of the next ~m~ lines contains three integers ~a, b, c~ representing an edge that connects vertex ~a~ and vertex ~b~ and has weight ~c~ ~(0 ≤ a, b < n , 0 < c < 10^9)~.

Output

• The required list of edges.

Sample Input

5 6
0 1 1
1 2 2
2 3 5
0 3 3
2 1 1
3 0 1

Sample Output

0 1 1
0 3 1
1 2 1
2 3 5

Notes

• https://drive.google.com/file/d/1Lsjs30v16V6l3yGzheGBbQ-MRIY4QBK4/view?usp=sharing