Sống ảo

Vào kỳ nghỉ sắp tới, Reimu và Reisen cùng nhau du lịch tới một vùng đất ma thuật. Vùng đất có \(n\) địa điểm tham quan, được kết nối bởi \(n - 1\) cây cầu, và bất kỳ \(2\) địa điểm nào cũng có thể đến được nhau bằng những cây cầu đó (nói cách khác, \(n\) địa điểm và \(n-1\) cây cầu tạo thành một cây). Nhằm tích góp cho việc bảo tồn vùng đất, chính quyền đã cho thu phí trên những cây cầu: cây cầu thứ \(i\) sẽ thu phí \(w_i\) xu mỗi lần đi qua (đi qua một cây cầu theo chiều nào cũng bị thu phí).

Reimu và Reisen vốn là những tín đồ sống ảo, vì vậy họ đã đặt ra lịch trình cho \(n\) ngày tại vùng đất như sau: ngày thứ \(i\) (\(1 \le i \le n\)), khởi hành từ địa điểm \(1\), họ sẽ quyết định đến thăm quan đúng \(i\) địa điểm (tính cả địa điểm xuất phát) để chụp ảnh check in. Để tiết kiệm chi phí, mỗi ngày hai người sẽ chọn đúng \(i\) địa điểm sao cho tổng chi phí di chuyển (bắt đầu từ địa điểm \(1\), đi qua các cây cầu để lần lượt thăm hết \(i\) địa điểm đã chọn, không cần quay lại địa điểm \(1\)) là nhỏ nhất.

Với mỗi ngày, hãy giúp Reimu và Reisen tìm số xu ít nhất họ phải chi ra để hoàn thành lịch trình.

Input

• Dòng đầu tiên gồm một số nguyên \(n\) (\(1 \le n \le 5000\)).

• \(n - 1\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(u, v, w\) (\(1 \le u, v \le n\), \(1 \le w \le 10^9\)) cho biết có cây cầu giữa hai địa điểm \(u\) và \(v\) với chi phí đi qua là \(w\) xu.

Dữ liệu đảm bảo \(n\) địa điểm và \(n - 1\) cây cầu đã cho tạo thành một cây.

Output

In ra \(n\) dòng. Dòng thứ \(i\) (\(1 \le i \le n\)) in ra một số nguyên là số xu ít nhất Reimu và Reisen phải chi để hoàn thành lịch trình của ngày thứ \(i\).

Example

Input:

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

Output:

0
2
4
6
10
14
18

Note

Ở ngày thứ \(5\), Reimu và Reisen sẽ chọn những địa điểm \(1, 2, 3, 5, 7\). Họ sẽ di chuyển theo lịch trình: \(1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 7\) (bắt đầu tại \(1\), đi đến \(2\), quay lại \(1\), rồi đi tiếp tới \(3\), \(5\) và dừng tại \(7\)), với tổng chi phí là \(2 + 2 + 2 + 2 + 2 = 10\) xu.