Một quốc gia có ~n~ thành phố và ~m~ tuyến đường hai chiều, tuyến đường thứ ~i~ nối hai thành phố ~u_i~, ~v_i~ và có chi phí bảo trì ~w_i~. Chính phủ muốn chọn một tập ~n-1~ tuyến đường để mọi thành phố vẫn liên thông với nhau và tổng chi phí là nhỏ nhất, tức là một cây khung nhỏ nhất.

Tuy nhiên, vì lý do chiến lược, ở mỗi phương án phân tích người ta quan tâm đến từng tuyến đường riêng lẻ. Độ ưu tiên của tuyến đường thứ ~i~ được định nghĩa là tổng chi phí nhỏ nhất của một cây khung bao trùm toàn bộ ~n~ thành phố và bắt buộc phải chứa tuyến đường thứ ~i~.

Yêu cầu: Với mỗi tuyến đường, hãy tính độ ưu tiên của nó.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(2 \le n \le 2 \cdot 10^5, n-1 \le m \le 3 \cdot 10^5)~;

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le w_i \le 10^9)~;

• Dữ liệu đảm bảo đồ thị liên thông và không có hai cạnh nào trùng nhau hoàn toàn.

Output

Gồm ~m~ dòng, dòng thứ ~i~ là độ ưu tiên của cạnh thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

6
6
8
8
6

Notes

• Một cây khung nhỏ nhất của đồ thị có chi phí ~6~, gồm các cạnh ~(1,3)~, ~(3,4)~, ~(1,2)~. Vì vậy ba cạnh trên đều có độ ưu tiên bằng ~6~.

• Cạnh ~(1,4)~ phải thay thế cạnh nặng nhất trên đường ~1 \rightarrow 3 \rightarrow 4~ trong cây khung nhỏ nhất, nên độ ưu tiên là ~8~. Cạnh ~(2,3)~ cũng có độ ưu tiên là ~8~.