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\to 1\to 2\to 1\to 3$. Tổng độ dài đường đi là $4+2+2+3=11$.