Một mạng máy tính có \(n\) máy tính và \(n-1\) kết nối giữa các cặp máy tính. Thông tin có thể được trao đổi giữa mọi cặp máy tính bằng các kết nối này.

Mỗi kết nối có một tốc độ truyền nhất định. Gọi \(d(a,b)\) là tốc độ truyền giữa hai máy tính \(a\) và \(b\), bằng tốc độ của kết nối chậm nhất trên đường đi giữa \(a\) và \(b\). Nhiệm vụ của bạn là tính tổng tốc độ truyền giữa tất cả các cặp máy tính.

Input

Dòng đầu tiên chứa số nguyên \(n\): số máy tính. Các máy tính được đánh số \(1,2,\dots,n\).

Sau đó có \(n-1\) dòng mô tả các kết nối. Mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(x\): có một kết nối giữa hai máy tính \(a\) và \(b\) với tốc độ truyền \(x\).

Output

In ra một số nguyên: tổng tốc độ truyền.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(1 \le x \le 10^6\)

Example

4
1 2 5
2 3 1
2 4 2

12

Giải thích: Hình sau tương ứng với dữ liệu mẫu: Ở đây \(d(1,2)=5\), \(d(1,3)=1\), \(d(1,4)=2\), \(d(2,3)=1\), \(d(2,4)=2\), và \(d(3,4)=1\), nên tổng tốc độ truyền là \(12\).