Cho đồ thị chứa ~n~ đỉnh ~m~ cạnh, là đồ thị vô hướng có trọng số với các cạnh không chứa khuyên, ví dụ như cạnh ~(u,u)~ là một khuyên.

Với mỗi cạnh ~(u, v)~, hãy tìm trọng số nhỏ nhất có thể của cây khung chứa cạnh ~(u, v)~. Nói cách khác, ta cần tìm trọng số của cây khung nhỏ nhất chứa cạnh ~(u,v)~.

Trọng số của cây khung là tổng trọng số của tất cả các cạnh có trong cây khung.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 ≤ n ≤ 2 \times 10^5,~ ~n - 1 ≤ m ≤ 2 \times 10^5)~ - số đỉnh và số cạnh trong đồ thị.

Mỗi dòng trong số ~m~ dòng tiếp theo chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.

Output

In ra ~m~ dòng. Dòng thứ ~i~ chứa trọng số của cây khung nhỏ nhất chứa cạnh thứ i.

Các cạnh được đánh số từ ~1~ đến ~m~ theo thứ tự xuất hiện trong đầu vào.

Sample Input

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

Sample Output

9
8
11
8
8
8
9