Cho đồ thị có trọng số gồm ~N~ đỉnh và ~N-1~ cạnh. Gọi ~D(i,j)~ là khoảng cách từ đỉnh ~i~ đến đỉnh ~j~ trên cây. (Lưu ý đường đi từ đỉnh ~i~ đến đỉnh ~j~ chỉ thăm mỗi đỉnh duy nhất một lần).

Tạo đồ thị có hướng mới gồm ~N~ đỉnh, với mỗi cặp đỉnh ~(i,j)~ nếu ~i < j~ thì thêm cạnh nối từ đỉnh ~i~ đến đỉnh ~j~ có trọng số là ~D(i,j)~.

Nhiệm vụ của bạn là hãy tìm đường đi ngắn nhất từ đỉnh ~1~ đến tất cả các đỉnh khác trong đồ thị mới tạo.

Input

• Dòng đầu gồm số nguyên ~N~ ~(2 \le N \le 8 \cdot 10^4)~.

• Dòng thứ ~i+1~ ~(1 \le i \le N-1)~ bao gồm ~3~ số nguyên: ~u_i, v_i, w_i~ ~(1 \le u_i < v_i \le N, |w_i| \le 10^9)~, với ý nghĩa có cạnh nối giữa ~u_i~ và ~v_i~ với trọng số ~w_i~. Tất cả các cạnh này mô tả cây ban đầu.

Output

Gồm ~N~ số nguyên, số nguyên thứ ~i~ tượng trưng cho đường đi ngắn nhất từ ~1~ đến ~i~ trên đồ thị mới.

Sample Input 1

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

Sample Output 1

0 -2 -3 1 -10

Notes

~1 \rightarrow 2~ với chi phí ~D(1,2) = -2~.

~1 \rightarrow 2 \rightarrow 3~ với chi phí ~D(1,2) + D(2,3) = -3~.

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~ với chi phí ~D(1,2) + D(2,3) + D(3,4) = 1~.

~1 \rightarrow 2 \rightarrow 3 \rightarrow 5~ với chi phí ~D(1,2) + D(2,3) + D(3,5) = -10~.