Các bạn tình nguyện viên Bedao quyết định di cư sang thành phố VNOI để sinh sống. Thành phố gồm ~n~ ngôi nhà và ~n - 1~ con đường hai chiều nối trực tiếp hai ngôi nhà trong thành phố. Hệ thống đường xá của thành phố VNOI rất tối ưu nên từ một ngôi nhà có thể đến bất kỳ ngôi nhà nào thông qua các con đường.

Gen mới gồm một số bạn tình nguyện viên, mỗi bạn sẽ được bố trí một ngôi nhà khác nhau. Hàng ngày, các sếp lớn Bedao đều đi qua nhà mỗi bạn để giám sát nên cần một cách bố trí tối ưu để tiết kiệm thời gian. Cụ thể, chi phí cho một cách bố trí ~k~ ngôi nhà là tổng độ dài đường đi ngắn nhất từ ngôi nhà ~1~ đi qua tất cả ~k~ ngôi nhà. Do số lượng các bạn Gen mới chưa được quyết định, các sếp muốn tìm ra các cách bố trí có chi phí nhỏ nhất cho tất cả ~n~ trường hợp: Gen mới gồm ~1~ bạn tình nguyện viên, ~2~ bạn tình nguyện viên, ~\cdots~, ~n~ bạn tình nguyện viên.

Input

Dữ liệu vào từ file văn bản migration.inp:

Dòng đầu tiên gồm hai số nguyên ~n~ (~1 \le n \le 5000~) — số ngồi nhà trong thành phố.

Trong ~n - 1~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên ~u_i~, ~v_i~ và ~w_i~ (~1 \le u_i, v_i \le n~, ~1 \le w_i \le 10^9~, ~u_i \ne v_i~) — con đường trực tiếp nối hai ngôi nhà ~u_i~ và ~v_i~ với thời gian di chuyển ~w_i~.

Dữ liệu đảm bảo rằng bố cục các ngôi nhà tạo thành cây, và từ một ngôi nhà có thể đến bất kỳ ngôi nhà nào chỉ thông qua các con đường.

Output

In ra file văn bản migration.out trên ~n~ dòng, dòng thứ ~i~ là chi phí nhỏ nhất của cách bố trí tối ưu ~i~ bạn tình nguyện viên vào các ngôi nhà.

Scoring

Sample Input 1

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

Sample Output 1

0
1
2
3
5
7
9

Notes

Trong ví dụ trên, với ~k = 5~, các sếp sẽ bố trí ~5~ bạn tình nguyện viên vào các ngôi nhà ~1, 2, 3, 5, 7~. Như vậy mỗi ngày các sếp chỉ cần di chuyển như sau: ~1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 7~ và đây là cách bố trí tối ưu.