Description

Input

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.

Output

Print one integer — the number of valid pairs of vertices.

7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1

34

Note

The picture corresponding to the first example: