There exists a tree with vertices and
bidirectional edges. Each edge
connects vertices
and
and has a length of
. A path between two distinct vertices
and
is valid if
is reachable from
and the edge lengths on the path from
to
form a non-decreasing sequence. Note that a path from
to
is considered the same as a path from
to
(whether valid or not). Given the number of vertices and edges of a tree, find the number of valid paths.
Constraints
Subtask 1 [20%]
All are distinct.
Subtask 2 [80%]
No additional constraints.
Input Specification
The first line contains a single integer , the number of vertices in the tree.
The next lines contain 3 integers
,
and
, representing a bidirectional edge from
to
of length
.
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 ,
and
. Notice that
and
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
Comments