Vào thế kỉ XXII, cuộc chiến tranh lạnh giữa hành tinh ~\mathrm{X}~ và hành tinh ~\mathrm{Y}~ đang diễn ra. Quốc vương của cả hai hành tinh đều đang ráo riết chạy đua vũ trang và do thám những thông tin của nhau để giành được lợi thế trước đối phương khi cuộc chiến tranh thực sự nổ ra.

Sau khi gửi rất nhiều gián điệp dến do thám, Quốc vương hành tinh ~\mathrm{Y}~ cuối cùng cũng đã nắm được toàn bộ tình hình mạng lưới giao thông trên hành tinh ~\mathrm{X}~. Hành tinh ~\mathrm{X}~ gồm ~n~ thành phố. Có ~m~ tuyến đường hai chiều, tuyến đường thứ ~i~ nối giữa hai thành phố ~u_{i}, v_{i}~ và có độ dài là ~w_{i}~. Đồng thời, không có hai tuyến đường nào nối cùng một cặp thành phố.

Đồng thời, Quốc vương hành tinh ~\mathrm{X}~ cũng đã lên kế hoạch xây dựng lại các tuyến đường trong trường hợp toàn bộ mạng lưới giao thông bị phá hủy bởi cuộc chiến trong tương lai. Một phương án xây dựng ~S~ là một tập con của ~m~ tuyến đường ban đầu, sao cho giữa hai thành phố bất kì vẫn có thể đi được đến nhau nếu chỉ sử dụng các tuyến đường trong tập ~S~. Chi phí của một phương án xây dựng ~S~ là tổng độ dài của các tuyến đường trong tập ~S~. Để tiết kiệm chi phí tối đa, Quốc vương hành tinh ~\mathrm{X}~ sẽ lựa chọn phương án xây dựng có chi phí nhỏ nhất.

Với những thông tin tình báo trên, Bộ chỉ huy đánh giá rằng độ quan trọng của tuyến đường thứ ~i~ là chi phí nhỏ nhất để xây dựng lại mạng lưới giao thông trong trường hợp tuyến đường thứ ~i~ bị tàn phá nặng nề và không thể xây dựng lại. Trong trường hợp không tồn tại phương án xây dựng nếu tuyến đường thứ ~i~ bị tàn phá, Bộ chỉ huy quy ước rằng độ quan trọng của tuyến đường thứ ~i~ là ~-1~ (nhằm kí hiệu rằng đây là thành phố trọng yếu).

Bộ chỉ huy quân sự đã giao cho Quang, một sĩ quan cấp cao, nhiệm vụ tính độ quan trọng của từng tuyến đường trên hành tinh ~\mathrm{X}~. Hãy giúp Quang hoàn thành nhiệm vụ được giao.

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương ~n, m(2 \leq n \leq 150000,1 \leq m \leq 300000)~ là số thành phố và số tuyến đường.
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo gồm ba số nguyên ~u_{i}, v_{i}~ và ~w_{i}\left(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i}\right.~, ~1 \leq w_{i} \leq 10^{6}~ ) mô tả tuyến đường thứ ~i~.

Kết quả:

• Ghi ra ~m~ dòng, dòng thứ ~i~ gồm một số nguyên là độ quan trọng của tuyến đường thứ ~i~.

Ví dụ:

Sample Input 1

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

Sample Output 1

8
9
6
6
8

Sample Input 2

7 10
1 2 5
1 3 3
2 3 10
2 4 6
2 5 4
3 6 9
3 7 1
4 5 7
5 6 2
6 7 8

Sample Output 2

24
26
21
22
24
21
28
21
27
21

Sample Input 3

4 2
1 2 1
3 4 2

Sample Output 3

-1
-1

Giải thích:

Hình vẽ bên dưới minh họa ví dụ thứ nhất (số được ghi trên cạnh là độ dài của tuyến đường). Ở ví dụ này, giả sử tuyến đường ~(1,3)~ bị tàn phá thì cách xây dựng có chi phí nhỏ nhất sẽ gồm các tuyến đường ~(1,2),(1,4)~ và ~(3,4)~. Cách xây dựng này có tổng chi phí ~3+4+2=9~. Do đó, độ quan trọng của tuyến đường ~(1,3)~ là 9.

Hình vẽ bên dưới minh họa ví dụ thứ hai.

Ràng buộc

• Có ~20 \%~ số điểm thỏa: ~n \leq 200, m \leq 500~;
• ~20 \%~ số điểm tiếp theo thỏa: ~m \leq n+100~;
• ~30 \%~ số điểm tiếp theo thỏa: ~w_{i} \leq 10~;
• ~30\%~ số điểm còn lại không có giới hạn gì thêm.