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>
//No sorceries shall prevail.
import java.util.*;
import java.io.*;
public class Main {

	static Scanner inp= new Scanner(System.in);
	static PrintWriter out= new PrintWriter(System.out);
	public static void main(String args[]) {		    	
	   	Main g=new Main();
	   	g.main();
	   	out.close();
	}

	static int n;
	static ArrayList<Pair> list[];
	static long dp[][];
	static boolean vis[];
	static boolean vis2[];
	
	//Main
	void main() {
		
		n=inp.nextInt();
		list=new ArrayList[n];
		for(int i=0;i<n;i++) {
			list[i]=new ArrayList<Pair>();
		}
		for(int i=0;i<n-1;i++) {
			int x=inp.nextInt()-1;
			int y=inp.nextInt()-1;
			int color=inp.nextInt();
			list[x].add(new Pair(y,color));
			list[y].add(new Pair(x,color));
		}
		long gg=0;
		dp=new long[n][2];
		gg+=forest(0);
		gg+=forest(1);
		for(int i=0;i<n;i++) {
			//System.out.println(dp[i][0]+" "+dp[i][1]);
			gg+=(dp[i][0]*dp[i][1]);
		}
		System.out.println(gg);
	}
	
	static long forest(int color) {
		vis=new boolean[n];
		vis2=new boolean[n];
		long gg=0;
		for(int i=0;i<n;i++) {
			if(!vis[i]) {
				long elements=dfs(i,color);
				gg+=((elements)*(elements-1));
				assignDp(i,elements-1,color);
			}
		}
		return gg;
	}
	
	static void assignDp(int i, long value, int color) {
		vis2[i]=true;
		dp[i][color]=value;
		for(Pair x: list[i]) {
			if(vis2[x.to] || x.color!=color) continue;
			assignDp(x.to,value,color);
		}
	}
	
	static long dfs(int i,int color) {
		long c=1;
		vis[i]=true;
		for(Pair x: list[i]) {
			if(vis[x.to] || x.color!=color) continue;
			c+=dfs(x.to,color);
		}
		return c;
	}
	
	
	static class Pair {
		int to, color;
		Pair(){
			
		}
		Pair(int x, int y){
			to=x;
			color=y;
		}
	}
		
}
