A tree with n vertices is given. The edges of the tree have a weight of 0 or 1 only. 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 ≤ n ≤ 105) in graph. It is followed by n - 1 lines containing the description of edges. Every line of description consists of three integer numbers: vertices connected by the edge (labelled from 1 to n) and edge's weight (0 or 1).

Output

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