Cho cây gồm ~ n ~ đỉnh và ~ n-1 ~ cạnh. Hãy tính tổng khoảng cách giữa mọi cặp đỉnh trên cây.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~ ~ ( n ≤ 100000 ) ~
• ~ n-1 ~ dòng tiếp theo mỗi dòng ghi 3 số ~ u, v, c ~ cho biết cạnh nối hai đỉnh ~ u ~ và ~ v ~ trên cây có trọng số ~ c ~. Lưu ý: các đỉnh được đánh số thứ tự từ 1 đến ~ n ~.

Kết quả

Ghi một số nguyên duy nhất cho biết tổng khoảng cách giữa mọi cặp đỉnh trên cây.

Ràng buộc

Ví dụ:

Input 1

4
1 2 2
2 3 2
3 4 2 

Output 1

20