(nttree.*)

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 \leq 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.

Ví dụ:

Input	Output
4 1 2 2 2 3 2 3 4 2	20