Cho cây có trọng số gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~. Bạn hãy tìm đường đi có độ dài nhỏ nhất đi qua tất cả các đỉnh của cây, mỗi đỉnh ít nhất một lần.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 2 \times 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~ và ~w~ mô tả cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~w~ ~(1 \le u,v \le n~ ~;~ ~1 \le w \le 10^9)~.
• Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây hợp lệ.

Output

• In ra độ dài nhỏ nhất của đường đi thỏa mãn.

Examples

Sample Input 1

3
1 2 2
3 1 4

Sample Output 1

6

Sample Input 2

4
4 1 4
1 2 2
3 1 3

Sample Output 2

11

Notes

Trong ví dụ thứ hai, một đường đi tối ưu như sau: \(4→1→2→1→3\). Tổng độ dài đường đi là ~4+2+2+3=11~.