Cho đồ thị có hướng có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Hãy in ra danh sách cạnh theo thứ tự trọng số tăng dần (nếu trọng số bằng nhau thì sắp xếp theo thứ tự xuất hiện).

Input

• Dòng đầu tiên gồm 2 số nguyên \(N\), \(M\) (\(N \leq 50\), \(M \leq 50\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v, c\) thể hiện cung nối từ đỉnh \(u\) đến đỉnh \(v\) có trọng số \(c\)

Output

In ra \(M\) dòng, mỗi dòng là thông tin của của cạnh thứ \(i\) sau khi được sắp xếp

Example

** Sample Input **

4 4
1 3 2
3 4 8
2 3 4
1 4 1

**Sample Output **

1 4 1
1 3 2
2 3 4
3 4 8