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 CF1156D {

    public static class Edge{
        int a, b;
        public Edge(int x, int y){
            this.a=x; this.b=y;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        ArrayList<Edge> arl0=new ArrayList<>();
        ArrayList<Edge> arl1=new ArrayList<>();
        int a,b,c;
        for (int i = 0; i < N-1; i++) {
            StringTokenizer st=new StringTokenizer(br.readLine());
            a=Integer.parseInt(st.nextToken())-1;
            b=Integer.parseInt(st.nextToken())-1;
            c=Integer.parseInt(st.nextToken());
            if(c==0){
                arl0.add(new Edge(a,b));
            }else{
                arl1.add(new Edge(a,b));
            }
        }
        int[] rank0=new int[N];
        int[] rank1=new int[N];
        int[] par0=new int[N];
        int[] par1=new int[N];
        int[] siz0=new int[N];
        int[] siz1=new int[N];
        for (int i = 0; i < N; i++) {
            par0[i]=i; par1[i]=i; siz0[i]=1; siz1[i]=1;
        }
        for (Edge e : arl0) {
            int aa=find(e.a,par0);
            int bb=find(e.b,par0);
            if(aa!=bb){
                if(rank0[aa]>rank0[bb]){
                    par0[bb]=aa; siz0[aa]+=siz0[bb];
                }else if(rank0[aa]==rank0[bb]){
                    par0[bb]=aa; rank0[aa]++; siz0[aa]+=siz0[bb];
                }else{
                    par0[aa]=bb; siz0[bb]+=siz0[aa];
                }
            }
        }
        for (Edge e : arl1) {
            int aa=find(e.a,par1);
            int bb=find(e.b,par1);
            if(aa!=bb){
                if(rank1[aa]>rank1[bb]){
                    par1[bb]=aa; siz1[aa]+=siz1[bb];
                }else if(rank1[aa]==rank1[bb]){
                    par1[bb]=aa; rank1[aa]++; siz1[aa]+=siz1[bb];
                }else{
                    par1[aa]=bb; siz1[bb]+=siz1[aa];
                }
            }
        }
        long ans=0;
        for (int i = 0; i < N; i++) {   
            ans+= (long) siz0[find(i,par0)]*siz1[find(i,par1)];
            
        }
        System.out.println(ans-N);
    }
    public static int find(int x, int[] par){
        if(par[x]==x)return x;
        int ans=find(par[x],par);
        par[x]=ans; return ans;
    }
}
