There exists a tree with $N$ vertices and $N-1$ bidirectional edges. Each edge $i$ connects vertices $u_i$ and $v_i$ and has a length of $l_i$. A path between two distinct vertices $u$ and $v$ is valid if $v$ is reachable from $u$ and the edge lengths on the path from $u$ to $v$ form a non-decreasing sequence. Note that a path from $u$ to $v$ is considered the same as a path from $v$ to $u$ (whether valid or not). Given the number of vertices and edges of a tree, find the number of valid paths.

Constraints

$1\le N\le 2\times {10}^5$

$1\le u_i,v_i\le N$

$1\le l_i\le {10}^9$

Subtask 1 [20%]

All $l_i$ are distinct.

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains a single integer $N$, the number of vertices in the tree.

The next $N-1$ lines contain 3 integers $u_i$, $v_i$ and $l_i$, representing a bidirectional edge from $u_i$ to $v_i$ of length $l_i$.

Output Specification

Output a single integer, the number of valid paths. Please note that the answer may not fit inside a 32-bit integer.

Note: You do not need to pass all sample cases to earn points on this problem.

Sample Input 1

3
1 2 4
1 3 4

Sample Output 1

3

Explanation for Sample Output 1

The three valid paths are $1⟶2$, $1⟶3$ and $3⟶1⟶2$. Notice that $3⟶1⟶2$ and $2⟶1⟶3$ are considered the same path.

Sample Input 2

5
1 2 7
1 3 2
2 4 9
2 5 5

Sample Output 2

9

Sample Input 3

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

Sample Output 3

30