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>
import java.util.*;
import java.io.*;

@SuppressWarnings("unchecked")
public class CF1156D {
	class DSU {
		int[] p, size;
		public DSU(int n) {
			p = new int[n];
			for(int i = 0 ; i < n ; i++) p[i] = i;
			size = new int[n];
			Arrays.fill(size, 1);
		}
		int find(int x) { return x == p[x] ? x : (p[x] = find(p[x])); }
		boolean union(int u, int v) {
			int p1 = find(u), p2 = find(v);
			if(p1 != p2) {
				p[p1] = p2;
				size[p2] += size[p1];
				return true;
			}
			return false;
		}
	}
	// 0 -> 0 -> 1 -> 1 this is okay
	// 1 -> 0 this is not okay
	public CF1156D() {
		FS scan = new FS();
		int n = scan.nextInt();
		DSU[] dsu = new DSU[] {new DSU(n), new DSU(n)};
		for(int i = 0 ; i < n - 1 ; i++) {
			int u = scan.nextInt() - 1, v = scan.nextInt() - 1, c = scan.nextInt();
			dsu[c].union(u, v);
		}
		boolean[] visited = new boolean[n];
		long res = 0;
		for(int i = 0 ; i < n ; i++) {
			long size0 = dsu[0].size[dsu[0].find(i)];
			long size1 = dsu[1].size[dsu[1].find(i)];
			res += size0 * size1 - 1;
		}
		System.out.println(res);
	}
	int abs(int x) { return max(x, -x); }
	int min(int a, int b) { return a < b ? a : b; }
	int max(int a, int b) { return a > b ? a : b; }
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF1156D(); }
}