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.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class D {

	static int N;
	static ArrayList<Edge> adj[];
	static Edge edges[];
	static boolean hasOne[];
	public static void main(String[] args) {
		JS in = new JS();
		N = in.nextInt();
		hasOne = new boolean[N];
		adj = new ArrayList[N];
		for(int i = 0; i < N; i++) adj[i]  = new ArrayList<Edge>();
		edges = new Edge[N-1];
		for(int i = 0; i < N-1; i++) {
			int a = in.nextInt()-1;
			int b = in.nextInt()-1;
			int v = in.nextInt();
			Edge e = new Edge(a,b,v,i);
			if(v == 1) {
				hasOne[a]=true;
				hasOne[b]=true;
			}
			edges[i] = e;
			adj[a].add(e);
			adj[b].add(e);
		}
		
		int comp[] = new int[N];
		int compSize[] = new int[N];
		boolean vis[] = new boolean[N];
		boolean proc[][] = new boolean[2][N];
		boolean isOne[] = new boolean[N];
		ArrayList<Edge> inComp[] = new ArrayList[N];
		for(int i = 0; i < N; i++) inComp[i] = new ArrayList<Edge>();
		
		int curComp = 0;
		for(int i = 0; i < N-1; i++) {
			if(vis[i]) continue;
			ArrayDeque<Edge> q = new ArrayDeque<Edge>();
			q.add(edges[i]);
			vis[i] = true;
			comp[i] = curComp;
			compSize[curComp]++;
			if(edges[i].v == 1) isOne[curComp] = true;
			
			while(!q.isEmpty()) {
				Edge e = q.poll();
				inComp[curComp].add(e);
				if(!proc[e.v][e.a]) {
					proc[e.v][e.a] = true;
					//go through a's edges
					for(Edge next : adj[e.a]) {
						if(vis[next.id]) continue;
						if(next.v != e.v) continue;
						vis[next.id] = true;
						comp[next.id] = curComp;
						compSize[curComp]++;
						q.add(next);
					}
				}
				
				if(!proc[e.v][e.b]) {
					proc[e.v][e.b] = true;
					//go through b's edges
					for(Edge next : adj[e.b]) {
						if(vis[next.id]) continue;
						if(next.v != e.v) continue;
						vis[next.id] = true;
						comp[next.id] = curComp;
						compSize[curComp]++;
						q.add(next);
					}
				}
			}
			
			
			curComp++;
		}
		
		long res = 0;
		int nVis[] = new int[N];
		int cVis[] = new int[N];
		Arrays.fill(nVis, -1);
		Arrays.fill(cVis, -1);
		
		
		for(int i = 0; i < N; i++) {
			if(isOne[i]) {
				long numNodes = compSize[i]+1;
				long numCon = 0;
				for(Edge e : inComp[i]) {
					if(nVis[e.a] != i) {
						nVis[e.a] = i;
						for(Edge e2 : adj[e.a]) {
							if(cVis[comp[e2.id]] != i && e2.v == 0) {
								cVis[comp[e2.id]] = i;
								numCon += compSize[comp[e2.id]];
							}
						}
					}
					if(nVis[e.b] != i) {
						nVis[e.b] = i;
						for(Edge e2 : adj[e.b]) {
							if(cVis[comp[e2.id]] != i && e2.v == 0) {
								cVis[comp[e2.id]] = i;
								numCon += compSize[comp[e2.id]];
							}
						}
					}
					
				}
				
//				System.out.println(i+" n="+numNodes+" c="+numCon);
				res += (numNodes*(numNodes-1));
				res += numCon*numNodes;			
			}
			else {
				long numNodes = compSize[i]+1;
//				System.out.println(i+" n="+numNodes);
				res += (numNodes*(numNodes-1));
			}
			
		}
		for(int i = 0; i < N; i++) {
			if(hasOne[i]) {
				for(Edge e : adj[i]) {
					if(e.v == 0) {
						res -= compSize[comp[e.id]];
						
						break;
					}
				}
			}
		}
		System.out.println(res);
		
	}

	static class Edge{
		int a,b;
		int v;
		int id;
		public Edge(int aa, int bb, int vv, int ii) {
			a=aa;
			b=bb;
			v=vv;
			id=ii;
		}
		public int to(int x) {
			return a^b^x;
		}
	}
	
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;
		
		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}
		
		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}
		
		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}
		
		public int nextInt() {
			return (int)nextLong();
		}
		
		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}
		
		public double nextDouble() {
		    while(c!='.'&&c!='-'&&(c <'0' || c>'9')) c = nextChar();
		    boolean neg = c=='-';
		    if(neg)c=nextChar();
		    boolean fl = c=='.';
		    double cur = nextLong();
		    if(fl) return neg ? -cur/num : cur/num;
		    if(c == '.') {
			double next = nextLong();
			return neg ? -cur-next/num : cur+next/num;
		    }
		    else return neg ? -cur : cur;
		}
		
		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}
		
		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
	
}
