Cho \(G\) là một đồ thị vô hướng liên thông có trọng số. Ngưỡng chấp nhận của cạnh \(e\) là số tự nhiên \(x\) lớn nhất không vượt quá \(10^9\), sao cho khi thay đổi trọng số của \(e\) thành \(z\) (và giữ nguyên trọng số các cạnh khác) thì tồn tại một cây khung nhỏ nhất của \(G\) chứa \(e\).

Yêu cầu: Hãy tìm ngưỡng chấp nhận của từng cạnh.

Input

• Gồm một dòng chứa hai số \(n,m\) là số đỉnh và số cạnh của đồ thị \(G\). Các đỉnh đánh số từ \(1\).

• \(m\) dòng tiếp theo mỗi dòng chứa \(3\) số \(u,v,w\) thể hiện một cạnh của \(G\).

Output

Ghi \(m\) dòng, mỗi dòng ghi ngưỡng chấp nhận của từng cạnh theo thứ tự đầu vào.

Ràng buộc

• \(1 ≤ n ≤ 10^5, n-1 ≤ m ≤ 10^6, 0 ≤ w ≤ 10^9\)

• Subtask 1: Có 50% số test với \(n≤1000, m≤10000\);

• Subtask 2: Có 50% số test không có ràng buộc gì thêm.

Sample Input

6 7 
1 2 2 
2 3 1 
3 4 0 
1 4 3 
3 5 20 
4 5 8 
3 6 14

Sample Output

3
3
3
2
8
20
1000000000