Unique Occurrences

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the number of vertices in the tree.

Each of the next $$$n-1$$$ lines contains three integers $$$v, u$$$ and $$$x$$$ ($$$1 \le v, u, x \le n$$$) — the description of an edge: the vertices it connects and the value written on it.

The given edges form a tree.

Output:

Print a single integer — the sum of $$$f(v, u)$$$ over all pairs of vertices $$$v$$$ and $$$u$$$ such that $$$v < u$$$.

Sample Input:

3
1 2 1
1 3 2

Sample Output:

4

Sample Input:

3
1 2 2
1 3 2

Sample Output:

2

Sample Input:

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

Sample Output:

14

Sample Input:

2
2 1 1

Sample Output:

1

Sample Input:

10
10 2 3
3 8 8
4 8 9
5 8 5
3 10 7
7 8 2
5 6 6
9 3 4
1 6 3

Sample Output:

120