Sau một sự cố an ninh mạng toàn cầu, mạng lưới máy chủ lõi gồm \(N\) máy chủ được kết nối với nhau dưới dạng một cấu trúc cây gồm \(N-1\) cáp nối quang. Mỗi cáp nối giữa máy chủ \(u\) và \(v\) có một băng thông truyền tải là \(w\). Để tái cấu trúc hệ thống một cách an toàn, bạn cần chọn ra đúng \(k\) cáp nối sao cho không có máy chủ nào kết nối trực tiếp với quá \(2\) cáp nối được chọn (tức là các cáp nối được chọn phải tạo thành một tập hợp các đường đi rời nhau về mặt đỉnh trên cây). Hãy xác định tổng băng thông lớn nhất có thể đạt được với mọi cấu hình chọn từ \(1\) đến \(N-1\) cáp nối.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \le N \le 300\)) — số lượng máy chủ.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\) và \(w\) (\(1 \le u, v \le N, |w| \le 10^9\)) mô tả một cáp nối giữa hai máy chủ \(u\) và \(v\) với băng thông \(w\).

Output

• In ra \(N-1\) số nguyên trên một dòng, số thứ \(k\) thể hiện tổng băng thông lớn nhất có thể đạt được khi chọn đúng \(k\) cáp nối thỏa mãn điều kiện. Nếu không thể chọn được đúng \(k\) cáp nối, in ra -1.

Example

5
1 2 5
2 3 10
3 4 -2
3 5 7

10 17 22 -1