Problem H. Highway cycle ≡

Statement

Young programmer Vasya lives in a city where streets can be represented by a tree. Each vertex of a tree correspond to an intersection, each edge — to a street. So number of streets in the city is 1 less than a number of intersections. It is possible to get from from each intersection to every other one by streets.

There are two kinds of streets — residential and office ones.

City administration wants to create a looping road, represented by a cycle of streets. To minimize spending, only a single road of either kind must be built, creating a cycle. To satisfy zoning regulations, cycle must consist of at least 4 streets and number of residential streets in the cycle must be equal to the number of office streets.

Young programmer Vasya is preparing a presentation for city mayor and wants to add a slide with the total number of ways to add a street to the city road system, while satisfying all requirements. Your program must calculate that number.

Input file format

Input file contains integer N — number of intersections in the city, followed by N − 1 triplets of integers u, v, c — numbers of intersections connected by street (u, v) and the kind of the street. c = 0 — residential street, c = 1 — office street.

Output file format

Output file must contain a single integer — number of ways.

Constraints

3 ≤ N ≤ 3000

0 ≤ u, v < N

Sample tests

4
0 1 0
1 2 1
2 3 1

1

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

2