Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~n-1~ cạnh thỏa mãn với mọi cặp đỉnh ~u,v~ của đồ thị tồn tại ít nhất ~1~ đường đi từ ~u~ đến ~v~. Các đỉnh của đồ thị được đánh số từ ~1~ đến ~n~, mỗi cạnh của đồ thị có một giá trị nguyên ~w~ (~w~ có thể âm). Định nghĩa ~d(u,v)~ là tổng các giá trị của các cạnh trong đường đi từ ~u~ đến ~v~ sao cho mỗi cạnh chỉ đi qua tối đa ~1~ lần (có thể chứng minh được tồn tại duy nhất ~1~ đường đi thỏa mãn điều kiện trên).

Tạo một đồ thị có hướng gồm ~n~ đỉnh từ đồ thị ban đầu như sau (mỗi cạnh của đồ thị mới cũng có một giá trị):

Với mọi cặp đỉnh ~(u,v)~ thỏa mãn ~u < v~, thêm một cạnh có hướng từ ~u~ đến ~v~ với giá trị là ~d(u,v)~.

Yêu cầu: Với mọi ~v~ từ ~1~ đến ~n~, tìm đường đi ngắn nhất từ ~1~ đến ~v~ trên đồ thị mới.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ là số đỉnh của đồ thị ban đầu ~(1 \le n \le 10^5)~.

~n-1~ dòng tiếp theo, mỗi dòng gồm ~3~ số ~u_i,v_i,w_i~ cho biết rằng cạnh thứ ~i~ của đồ thị ban đầu là ~(u_i,v_i)~ có giá trị là ~w_i~ ~(1 \le u_i,v_i \le n, -10^6 \le w_i \le 10^6)~.

Output

In ra ~n~ số ~d_1,\dots,d_n~ trên cùng một dòng, trong đó ~d_i~ là đường đi ngắn nhất từ ~1~ đến ~i~ trên đồ thị mới, các số tách nhau bởi một dấu cách.

Scoring

Sample Input 1

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

Sample Output 1

0 -1 -4 -5 -7 -3

Sample Input 2

5
3 1 0
1 4 2
4 2 -4
2 5 1

Sample Output 2

0 -2 -4 -6 -9

Sample Input 3

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

Sample Output 3

0 -2 -9 -15 -12