Công ty vận tải AZ nhận chở hàng cho ~n~ xã miền núi được đánh số từ ~1~ đến ~n~. Các xã nối với nhau bằng ~m~ con đường hai chiều. Con đường thứ ~j~ nối giữa hai xã ~(x_j, y_j)~ và có độ dốc ~w_j~. Giữa hai xã có thể có nhiều con đường khác nhau và độ dốc của chúng không nhất thiết khác nhau. Không có con đường nào vòng trực tiếp về đúng xã nó xuất phát.

Xe chở hàng là loại xe container có đầu kéo chuyên dụng. Chi phí một chuyến đi được tính bằng độ dốc cao nhất mà xe phải vượt qua trong hành trình.

Tài xế có thể đi vòng hoặc đi qua lại một xã nhiều lần để đi đến đích.

Yêu cầu: Với mỗi kho hàng tại xã ~u~, hãy tính tổng chi phí thấp nhất đến ~n-1~ xã còn lại.

Input

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

• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~x_j, y_j, w_j~ ~(1 \le x_j, y_j \le n; x_j \ne y_j; 1 \le w_j \le 10^9)~.

Output

Một dòng chứa ~n~ số nguyên, số thứ ~u~ là tổng chi phí thấp nhất ứng với kho hàng đặt tại xã ~u~. Khi ~n=1~ thì không có chuyến nào, in ra số ~0~.

Scoring

Sample Input 1

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

Sample Output 1

15 12 12 13

Sample Input 2

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

Sample Output 2

21 21 24 20 20

Sample Input 3

3 4
1 2 9
1 2 2
2 3 5
1 3 8

Sample Output 3

7 7 10

Notes

Ví dụ 1 khi đặt kho hàng tại xã ~2~:

• Chuyến đi từ kho hàng qua xã ~1~ có hành trình ~2 \rightarrow 1~ với chi phí nhỏ nhất là ~5~.

• Chuyến đi từ kho hàng qua xã ~3~ có hành trình ~2 \rightarrow 3~ với chi phí nhỏ nhất là ~3~.

• Chuyến đi từ kho hàng qua xã ~4~ có hành trình ~2 \rightarrow 3 \rightarrow 4~ với chi phí nhỏ nhất là ~4~.

Vậy tổng chi phí vận chuyển đến các xã còn lại là: ~5+3+4=12~.