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

public class A {

	static ArrayList<edge>[] adj;
	static int []dp,ones;
	
	static void dfs1(int u,int p) {
		
		for(edge nxt:adj[u])
		{
			int v=nxt.v,t=nxt.t;
			if(v!=p) {
				dfs1(v,u);
				if(t==1) {
					dp[u]+=1+ones[v];
					ones[u]+=1+ones[v];
				}
				else
					dp[u]+=1+dp[v];
			}
			
		}
	}
	static long dfs2(int u,int p,int t) {
		
		if(p!=-1)
		{
			if(t==0)
				dp[u]=dp[p];
			else {
				dp[u]+=ones[p]-(ones[u]);
				ones[u]+=ones[p]-(ones[u]);
			}
				
		}
		
		long ans=dp[u];
		for(edge nxt:adj[u])
		{
			int v=nxt.v;
			if(v!=p) 
				ans+=dfs2(v,u,nxt.t);
		}
		return ans;
		
	}
		public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		adj=new ArrayList[n];
		dp=new int [n];
		ones=new int [n];
		
		for(int i=0;i<n;i++) {
			adj[i]=new ArrayList();
			
		}
		for(int i=1;i<n;i++)
		{
			int u=sc.nextInt()-1,v=sc.nextInt()-1,t=sc.nextInt();
			adj[u].add(new edge(v,t));
			adj[v].add(new edge(u,t));
		}
		dfs1(1,-1);
		
		out.println(dfs2(1,-1,-1));
		out.close();

	}

	static class edge {
		int v, t;

		edge(int a, int b) {
			v = a;
			t = b;
		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

	}

}