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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.*;


public class ForcesC {

	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

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

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
		static class DJSet
		{ 
		    int[] rank;
		    int[] size;
		    int[] parent; 
		    int n; 
		  
		  
		    public DJSet(int n) 
		    { 
		        rank = new int[n]; 
		        parent = new int[n]; 
		        size = new int[n];
		        this.n = n; 
		        makeSet(); 
		    } 
		  
		   
		    void makeSet() 
		    { 
		        for (int i=0; i<n; i++) 
		        { 
		            size[i] = 1;
		            parent[i] = i; 
		        } 
		    } 
		  
		   
		    int find(int x) 
		    { 
		       
		        if (parent[x]!=x) 
		        { 
		            parent[x] = find(parent[x]); 
		  
		        } 
		  
		        return parent[x]; 
		    } 
		  
		   
		    void union(int x, int y) 
		    { 
		       
		        int xRoot = find(x), yRoot = find(y); 
		  
		        if (xRoot == yRoot) 
		            return; 
		  
		        
		        if (rank[xRoot] < rank[yRoot]) {
		  
		           
		            parent[xRoot] = yRoot; 
		            size[yRoot]+=size[xRoot];
		       
		        }else if (rank[yRoot] < rank[xRoot]) {
		 
		            parent[yRoot] = xRoot; 
		            size[xRoot]+=size[yRoot];
		        } else 
		        { 
		            
		            parent[yRoot] = xRoot; 
		            size[xRoot]+=size[yRoot];
		            rank[xRoot] = rank[xRoot] + 1; 
		        } 
		    } 
		} 

	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long)(1e9+7);
	static FastReader sc = new FastReader();
   // static List<Integer>[] edge ;
	public static void main(String[] args) {
		int n = sc.nextInt();
		List<Integer>[] one = new ArrayList[n+1];
		DJSet dsu = new DJSet(n+1);   
		for(int i=0;i<=n;++i) {
			one[i] = new ArrayList<>();
		}
		for(int i=0;i<n-1;++i) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int c = sc.nextInt();
			if(c == 1) {
				one[u].add(v);
				one[v].add(u);
			}else {
				dsu.union(u, v);
			}
		}
		long ans = 0;
		
		List<List<Integer>> cmp = getComponents(one,n);	
		for(List<Integer> x : cmp) {
			long sz = x.size();
			ans+=(sz-1)*sz;
			for(int i : x) {
				long szz = dsu.size[dsu.find(i)];
				ans+=(szz-1)*sz;
				
			}
		}
		out.println(ans);
		out.close();
		
	}
	
	private static List<List<Integer>> getComponents(List<Integer>[] edges, int n) {
		List<List<Integer>> output = new ArrayList<>();
		boolean[] visited = new boolean[n+1];
		for(int i=1;i<=n;++i) {
			if(!visited[i]) {
				List<Integer> component = new ArrayList<>();
				dfs(edges,component,visited,i);
				output.add(component);
			}
		}
		return output;
	}

	private static void dfs(List<Integer>[] edges, List<Integer> component, boolean[] visited, int v) {
		
		visited[v] = true;
		component.add(v);
		for(int i=0;i<edges[v].size();++i) {
			int adjV = edges[v].get(i);
			if(!visited[adjV])
				dfs(edges,component,visited,adjV);
		}
	}
}