Cho một đồ thị vô hướng có trọng số, hãy xác định với mỗi cạnh chi phí của cây khung nhỏ nhất nếu cạnh đó bắt buộc phải được đưa vào cây khung.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số đỉnh và số cạnh. Các đỉnh được đánh số \(1,2,\dots,n\).

\(m\) dòng tiếp theo mô tả các cạnh. Mỗi dòng chứa ba số nguyên \(a\), \(b\), \(w\): có một cạnh giữa hai đỉnh \(a\) và \(b\) với trọng số \(w\).

Bạn có thể giả sử rằng đồ thị liên thông và đơn, và mỗi cạnh xuất hiện nhiều nhất một lần trong đồ thị.

Output

Với mỗi cạnh theo thứ tự nhập, in ra chi phí cây khung nhỏ nhất khi cạnh đó được chọn.

Constraints

• \(1 \le n \le 10^5\)

• \(1 \le m \le 2 \cdot 10^5\)

• \(1 \le a,b \le n\)

• \(1 \le w \le 10^9\)

Example

5 6
1 2 4
1 3 2
2 4 2
3 4 1
3 5 4
4 5 3

10
8
8
8
9
8