Cây khung chứa cạnh cho trước

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh, cạnh thứ $i$ nối hai đỉnh $u_i\ne v_i$ và có trọng số $w_i$. Giữa hai đỉnh có thể có nhiều cạnh.

Một cây khung là một tập $n-1$ cạnh nối liền mọi đỉnh; trọng số của cây khung là tổng trọng số các cạnh của nó. Với mỗi cạnh $i$, hãy tìm trọng số nhỏ nhất của một cây khung bắt buộc phải chứa cạnh $i$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ là trọng số nhỏ nhất của một cây khung chứa cạnh $i$.

Ràng buộc

• $2\le n\le 5·{10}^4$
• $n-1\le m\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$, $1\le w_i\le {10}^9$
• Đồ thị liên thông.

Ví dụ