Cho một cây n đỉnh được đánh số từ 0 đến n-1. Hãy tính tổng khoảng cách giữa mọi cặp đỉnh trên cây.

Input

• Dòng đầu tiên ghi số nguyên dương n (n≤10000)
• n-1 dòng tiếp theo mỗi dòng ghi 3 số u,v,w thể hiện một cạnh của cây có 2 đỉnh là u,v và trọng số là w

Output

• Một dòng duy nhất ghi kết quả tìm được (kết quả thuộc phạm vi số nguyên 64-bit)

Example

Input
2  
0 1 1  

Output
1