Cho đơn đồ thị vô hướng, liên thông ~G = (V, E)~ có trọng số, ~|V| = n~ được gọi là tập đỉnh, ~|E| = m~ được gọi là tập các cạnh của ~G~, ví dụ như hình vẽ sau:

Bi muốn giải bài toán tìm cây khung nhỏ nhất nhưng mỗi cây phải chứa lần lượt các cạnh ~e \in E~ của đồ thị.

Hãy lập trình giải quyết nội dung trên giúp Bi

Input

Dòng thứ nhất chứa hai số nguyên ~n, m~ là số đỉnh và số cạnh của đồ thị thỏa ~1 \le n \le 2.10^5; n-1 \le m \le 2.10^5~.

~m~ dòng kế tiếp biểu diễn cạnh nối giữa hai đỉnh ~x_i, y_i~ của đồ thị và trọng số ~w_i~ trên cạnh của nó theo thứ tự từ ~1~ đến ~m~ của ~E~, thỏa ~1 \le x_i \neq y_i \le n; 1 \le w_i \le 10^9~.

Output

In ra ~m~ dòng tương ứng là tổng độ dài của cây khung nhỏ nhất mà có chứa cạnh ~e_i~ theo thứ tự.

Samples

Sample Input 1

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 1

9
8
11
8
8
8
9