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