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 \longrightarrow 2~, ~1 \longrightarrow 3~ and ~3 \longrightarrow 1 \longrightarrow 2~. Notice that ~3 \longrightarrow 1 \longrightarrow 2~ and ~2 \longrightarrow 1 \longrightarrow 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