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 Main {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n=Integer.parseInt(f.readLine());
        Arrays.fill(size0,1);
        Arrays.fill(size1,1);
        for(int i=0;i<n;i++){
            graph[i]=new ArrayList<>();
            par1[i]=i;
            par0[i]=i;
        }
        for(int i=0;i<n-1;i++){
            StringTokenizer st=new StringTokenizer(f.readLine());
            int a= Integer.parseInt(st.nextToken())-1;
            int b=Integer.parseInt(st.nextToken())-1;
            int c=Integer.parseInt(st.nextToken());
//            graph[a].add(new edge(b,c));
//            graph[b].add(a,c);
            if(c==0) {
                union(a,b,par0,0);
            }
            else {
                union(a,b,par1,1);
            }
        }
        long ans=0;
        boolean found0[]=new boolean[200005];
        boolean found1[]=new boolean[200005];
        for(int i=0;i<n;i++){
            int a=find(i,par0);
            if(!found0[a]){
                ans+=(size0[a]*(size0[a]-1));
                found0[a]=true;
            }
            int b=find(i,par1);
            if(!found1[b]){
                ans+=(size1[b]*(size1[b]-1));
                found1[b]=true;
            }
        }
        for(int i=0;i<n;i++){
            int a=find(i,par0);
            int b=find(i,par1);
            ans+=(size0[a]-1)*(-1+size1[b]);
        }
        System.out.println(ans);
        f.close();
        out.close();
    }
    static void union(int x, int y,int par[],int type){
        x=find(x,par);
        y=find(y,par);

        if(x==y)return;
        //multiply because next vals
        if(type==0){
            size0[x]+=size0[y];
        }
        else{
            size1[x]+=size1[y];
        }
        par[y]=x;
    }
    static int[]par1=new int[220000];
    static int[]par0=new int[220000];
    static long[]size1=new long[220000];
    static long[]size0=new long[220000];
    static int find(int x,int[]par){
        if(x==par[x])return x;
        return par[x]=find(par[x],par);
    }

    static ArrayList<Integer>[]graph=new ArrayList[220000];
}
class edge{
    int to,val;
    edge(int a, int b){
        to=a;val=b;
    }
}