Problem Description

Snuke lives in a country with \( N \) stations. There are only two railway companies in this country, Company \( A \) and Company \( B \), each building their own tracks independently.

These tracks connect two stations, and each track has a length. Both railway companies ensure that there is exactly one path between any two stations without using the same track more than once.

Both companies set the fare between the \( i \)-th station and the \( j \)-th station as the maximum distance between adjacent stations on the path.

Snuke wondered which railway company is better for traveling between different stations. He thought that there might be some pairs of stations where the fare is the same regardless of which company is used. He wants to find the number of such pairs of stations.

So, how many pairs of stations have the same fare regardless of which company is used?

Input Format

None

Output Format

Output the number of pairs of stations where the fare is the same regardless of which railway company is used. Do not forget to add a newline at the end.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1

Sample Input #2

None

Sample Output #2

2

Sample Input #3

None

Sample Output #3

10

Notes/Hints

Scoring

This problem has partial scoring. If you solve the dataset that satisfies the additional constraint below correctly, you will be awarded 40 points.

• The same railway company does not build tracks of the same length.

Sample Explanation 1

Sample Explanation 2

Sample Explanation 3

This satisfies the constraint for partial points.

见题面 Input 部分

见题面 Output 部分