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.*;

public class Main {
	public static void main(String args[]) { new Main().WORK(); }
	
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	
	final int N = (int)(2e5+10);
	
	class PII {
		int v, w;
		PII(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}
	
	boolean[] vis = new boolean[N];
	int[][] up = new int[N][2], dw = new int[N][2];
	ArrayList<PII>[] G = new ArrayList[N];
	long ans = 0;
	
	void dfs_1(int u, int fa) {
		for(PII t:G[u]) if(t.v != fa) {
			dfs_1(t.v, u);
			if(t.w == 0) dw[u][0] += dw[t.v][0]+1;
			else dw[u][1] += dw[t.v][0]+dw[t.v][1]+1;
		}
	}
	
	void dfs_2(int u, int fa) {
//		out.printf("u=%d %d %d %d %d\n", u, up[u][0], up[u][1]
//				, dw[u][0], dw[u][1]);
		ans += up[u][0]+up[u][1]+dw[u][0]+dw[u][1];
		for(PII t:G[u]) if(t.v != fa) {
			if(t.w == 0) up[t.v][0] += up[u][0]+dw[u][0]-dw[t.v][0];
			else up[t.v][1] += up[u][0]+up[u][1]+
					dw[u][0]-dw[t.v][0]+dw[u][1]-dw[t.v][1];
			dfs_2(t.v, u);
		}	
	}
	
	void WORK() {
		int n = in.nextInt();
		for(int i = 1; i <= n; i++) G[i] = new ArrayList<>();
		for(int i = 1; i < n; i++) {
			int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
			G[u].add(new PII(v, w));
			G[v].add(new PII(u, w));
		}
		dfs_1(1, 0); dfs_2(1, 0);
		out.println(ans);
		out.flush();
	}
}