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 EdA {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner sc;
    public static PrintWriter out;
    static ArrayList<ArrayList<Integer>> tree;
    static Map<Long, Integer> weightMap;
    static int[][] dp;
    static int[][] actualdp;
	public static void main(String[] omkar) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
 		int n = sc.nextInt();
 		tree = new ArrayList<ArrayList<Integer>>();
 		for(int j = 0;j<=n;j++){
 			tree.add(new ArrayList<Integer>());
 		}
 		weightMap = new HashMap<>();
 		for(int j =0 ;j<n-1;j++){
 			int v1 = sc.nextInt();
 			int v2 = sc.nextInt();
 			tree.get(v1).add(v2);
 			tree.get(v2).add(v1);
 			int c = sc.nextInt();
 			weightMap.put((long)(v1)*200001L+(long)(v2), c);
 			weightMap.put((long)(v2)*200001L+(long)(v1), c);
 		}
 		dp = new int[n+1][2];
 		dfs(1, -1);
 		actualdp = new int[n+1][2];
 		for(int j = 0;j<=n;j++){
 			actualdp[j][0] = dp[j][0];
 			actualdp[j][1] = dp[j][1];
 		}
 		actualdfs(1, -1);
 		long sum =0 ;
 		for(int j = 1;j<=n;j++){
 			sum+=(long)(actualdp[j][0]);
 		}
 		out.println(sum-n);
 		out.close();
 		
 		
 	}
	public static void dfs(int v, int p){
		for(int child : tree.get(v)){
			if (child == p)
				continue;
			dfs(child, v);
		}
		dp[v][0] = 1;
		dp[v][1] = 1;
		for(int child : tree.get(v)){
			if (child == p)
				continue;
			if (getWeight(v, child) == 1){
				dp[v][0]+=dp[child][1];
				dp[v][1]+=dp[child][1];
			}
			else{
				dp[v][0]+=dp[child][0];
			}
		}
	}
	public static void actualdfs(int v, int p){
		for(int child : tree.get(v)){
			if (child == p)
				continue;
			if (getWeight(child, v) == 1){
				actualdp[child][0]+=(actualdp[v][1]-dp[child][1]);
				actualdp[child][1]+=(actualdp[v][1]-dp[child][1]);
			}
			else{
				actualdp[child][0]+=(actualdp[v][0]-dp[child][0]);
			}
			actualdfs(child, v);
		}
	}
	public static int getWeight(int v1, int v2){
		return weightMap.get((long)(v1)*200001L+(long)(v2));
	}
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<Integer>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is