You are given a tree (an undirected connected acyclic graph) consisting of n vertices and n - 1 edges. A number is written on each edge, each number is either 0 (let's call such edges 0-edges) or 1 (those are 1-edges).

Let's call an ordered pair of vertices (x, y) (x ≠ y) valid if, while traversing the simple path from x to y, we never go through a 0-edge after going through a 1-edge. Your task is to calculate the number of valid pairs in the tree.

Input

The first line contains one integer n (2 ≤ n ≤ 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 ≤ x_i, y_i ≤ n, 0 ≤ c_i ≤ 1, x_i ≠ 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.

Example

Input


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


Output


34

Note

The picture corresponding to the first example:

<image>
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF1156D {
	static int[][] dsu, kk;
	static int find(int c, int i) {
		return dsu[c][i] < 0 ? i : (dsu[c][i] = find(c, dsu[c][i]));
	}
	static void join(int c, int i, int j) {
		i = find(c, i);
		j = find(c, j);
		if (i == j)
			return;
		if (dsu[c][i] > dsu[c][j]) {
			dsu[c][i] = j;
			kk[c][j] += kk[c][i];
		} else {
			if (dsu[c][i] == dsu[c][j])
				dsu[c][i]--;
			dsu[c][j] = i;
			kk[c][i] += kk[c][j];
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dsu = new int[2][n];
		kk = new int[2][n];
		Arrays.fill(dsu[0], -1);
		Arrays.fill(dsu[1], -1);
		Arrays.fill(kk[0], 1);
		Arrays.fill(kk[1], 1);
		for (int h = 0; h < n - 1; h++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken()) - 1;
			int j = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken());
			join(c, i, j);
		}
		long ans = 0;
		for (int i = 0; i < n; i++) {
			int r0 = find(0, i);
			int r1 = find(1, i);
			ans += (long) kk[0][r0] * kk[1][r1] - 1;
		}
		System.out.println(ans);
	}
}
