XOR Sum

The tree with $n$ vertices is given. The edges of the tree have weights of only $0$ or $1$. Let’s find the XOR sum between all pairs of vertices. Compute the sum of all XOR sums.

Input

The first line contains the number of vertices $n(2\le n\le 10^5)$ in the graph. The next $n-1$ lines describe the edges. Each line contains three integers: the numbers of the vertices connected by the edge (vertices are numbered from $1$ to $n$) and the weight of the edge ($0$ or $1$).

Output

Print the sum of XOR sums between all pairs of vertices.

Examples