Cho một cây gồm \(N\) đỉnh. Mỗi cạnh của cây được ghi một giá trị nguyên (màu).

Gọi \(f(v, u)\) là số lượng giá trị xuất hiện đúng một lần trên các cạnh của đường đi đơn giữa hai đỉnh \(v\) và \(u\).

Yêu cầu: Tính tổng của \(f(v, u)\) qua tất cả các cặp đỉnh \((v, u)\) thỏa mãn \(1 \leq v < u \leq N\):

Input

• Dòng đầu tiên chứa một số nguyên \(N\) (\(2 \leq N \leq 5\cdot 10^5\)) là số lượng đỉnh của cây.
• Mỗi dòng trong \(N - 1\) dòng tiếp theo chứa ba số nguyên \(v\), \(u\) và \(x\) (\(1 \leq v < u \leq N\)) mô tả một cạnh kết nối giữa hai đỉnh \(v\), \(u\) và giá trị (màu) \(x\) được ghi trên cạnh đó.
• Các cạnh đã cho đảm bảo tạo thành một cây.

Output

• In ra một số nguyên duy nhất là tổng \(f(v, u)\) qua tất cả các cặp đỉnh \(v < u\).

Example

3
1 2 1
1 3 2

4

5
1 4 4
1 2 3
3 4 4
4 5 5

14