Cho một cây 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. 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~ với ~2 ≤ N ≤ 8.10^4~. Tiếp theo, dòng thứ ~i~ với ~1 ≤ i ≤ N - 1~ bao gồm 3 số nguyên: ~u_i, v_i, w_i~ với ~1 ≤ u_i < v_i ≤ N, |w_i | ≤ 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~ cho biết cho đường đi ngắn nhất từ 1 đến i trên đồ thị mới.

Sample input

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

Sample output

0 -2 -3 1 -10

Giải thích

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