Thành phố vừa hết giãn cách do dịch bệnh đã qua đi nên các tuyến đường đông đúc trở lại. Các hàng quán, khu chợ, siêu thị cũng trở nên tấp nập và nhộn nhịp như những năm trước đây. Tuy nhiên, để tránh tình trạng kẹt xe và ùn tắc ở các tuyến đường, các thông số thống kê được các nhà chức trách thu thập để điều phối lưu lượng giao thông hợp lý hơn.

Cụ thể, thành phố được mô tả dưới dạng một đồ thị gồm ~n~ đỉnh và ~m~ cạnh tương ứng với ~n~ địa điểm và ~m~ tuyến đường hai chiều ~(u,v)~. Trên mỗi cạnh có một trọng số ứng với lưu lượng giao thông tại tuyến đường đó. Biết rằng, không có tuyến đường nào mà hai đầu của tuyến đường đó là cùng một địa điểm, và không có hai địa điểm nào được liên kết bởi nhiều hơn một tuyến đường. Đồng thời, tại một địa điểm bất kỳ có thể di chuyển được đến tất cả các địa điểm khác thông qua một hoặc nhiều tuyến đường.

Các nhà chức trách muốn biết rằng liệu với mỗi tuyến đường ~(u,v)~, có thể chọn thêm ~n-2~ tuyến đường khác sao cho ~n~ địa điểm vẫn được liên kết với nhau và có tổng lưu lượng là nhỏ nhất.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~ – là số lượng địa điểm và số lượng tuyến đường trong thành phố.

~m~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, u_i ≠ v_i, 1 \le w_i \le 10^9)~ – biểu diễn hai địa điểm đầu mút của tuyến đường thứ i và lưu lượng của tuyến đường đó.

Output

Gồm ~m~ dòng, dòng thứ ~i~ chứa tổng lưu lượng nhỏ nhất của ~n-1~ tuyến đường liên kết ~n~ địa điểm và có chứa tuyến đường thứ ~i~.

Lưu ý: Các địa điểm và tuyến đường được đánh số thứ tự từ ~1~.

Sample Input

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

Sample Output

8
9
8
8
8
11
11
13
11
14

Subtasks:

• ~40\%~ số lượng test có ~1 \le n \le 50, n-1 \le m \le n×(n-1)/2, w_i \le 100~
• ~40\%~ số lượng test có ~1 \le n \le 10^4, n-1 \le m \le min(n×(n-1)/2, 2×10^5), w_i \le 10^5~
• ~20\%~ số lượng test có ~1 \le n, m \le 2×10^5, w_i \le 10^9~