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[]) {new Main().run();}

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    void run(){
        work();
        out.flush();
    }
    long mod=1000000007;
    long gcd(long a,long b) {
        return a==0?b:gcd(b%a,a);
    }
    final long inf=Long.MAX_VALUE;
    int[][] dp;//0,1,01,10,101
    ArrayList<long[]>[] graph;
    long ret;
    void work() {
        int n=ni();
        dp=new int[n][5];
        graph=ngw(n,n-1);
        dfs(0,-1);
        out.println((long)n*(n-1)-ret);
    }

    private void dfs(int node, int pre) {
        for(long[] g:graph[node]){
            int nn=(int)g[0];
            int t=(int)g[1];
            if(pre!=nn){//0,1,01,10,101
                dfs(nn,node);
                if(t==0){
                    dp[node][0]+=dp[nn][0]+1;
                    dp[node][3]+=dp[nn][1]+dp[nn][3];
                    dp[node][4]+=dp[nn][2]+dp[nn][4];
                }else{
                    dp[node][1]+=dp[nn][1]+1;
                    dp[node][2]+=dp[nn][0]+dp[nn][2];
                    dp[node][4]+=dp[nn][3]+dp[nn][4];
                }
            }
        }
        ret+=2*dp[node][4]+dp[node][2]+dp[node][3];
        long v1=0,v2=0,v3=0,v4=0,v5=0;//0,1,01,10,101
        v1+=dp[node][2]+dp[node][4];
        v2+=dp[node][0]+dp[node][2]+dp[node][3]+dp[node][4];
        v3+=dp[node][0]+dp[node][2]+dp[node][3]+dp[node][4];
        v4+=dp[node][0]+dp[node][1]+dp[node][2]+dp[node][3]+dp[node][4];
        v5+=dp[node][0]+dp[node][1]+dp[node][2]+dp[node][3]+dp[node][4];
        for(long[] g:graph[node]){
            int nn=(int)g[0];
            int t=(int)g[1];
            if(nn!=pre){
                long m1=0,m2=0,m3=0,m4=0,m5=0;
                if(t==0){
                    m1+=dp[nn][0]+1;
                    m4+=dp[nn][1]+dp[nn][3];
                    m5+=dp[nn][2]+dp[nn][4];
                }else{
                    m2+=dp[nn][1]+1;
                    m3+=dp[nn][0]+dp[nn][2];
                    m5+=dp[nn][3]+dp[nn][4];
                }
                ret+=m1*(v1-m3-m5);
                ret+=m2*(v2-m1-m3-m4-m5);
                ret+=m3*(v3-m1-m3-m4-m5);
                ret+=m4*(v4-m1-m2-m3-m4-m5);
                ret+=m5*(v5-m1-m2-m3-m4-m5);
            }
        }
    }

    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
            graph[(int)s].add(new long[] {e,w});
            graph[(int)e].add(new long[] {s,w});
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }

    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A=new long[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextLong();
        }
        return A;
    }
    private int[] nia(int n) {
        int[] A=new int[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextInt();
        }
        return A;
    }
}

class FastReader
{
    BufferedReader br;
    StringTokenizer st;

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


    public String next()
    {
        while(st==null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

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

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