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.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 998244353;
    long fac[]= new long[3000];
    public  void solve() throws IOException 
    {
      

      int n = readInt();

      ArrayList<edge> arr[]=new ArrayList[n+1];

      for(int i=1;i<=n;i++)
      {
        arr[i]= new ArrayList<edge>();
      }
     //  boolean check[][]=new boolean[n+1][2];
      for(int i =0;i<n-1;i++)
      {
        int u = readInt();
        int v = readInt();
        int w = readInt();
        arr[u].add(new edge(v,w));
        arr[v].add(new edge(u,w));
        
      }

      int parent1[]=new int[n+1];
      int parent2[]=new int[n+1];

      for(int i =1;i<=n;i++)
        parent1[i]=i;

      for(int i =1;i<=n;i++)
        parent2[i]=i;


      int size1[] =new int[n+1];
      int size2[]=new int[n+1]; 

      Arrays.fill(size1,1);
      Arrays.fill(size2,1);

      for(int i=1;i<=n;i++)
      {
         for(int j =0;j<arr[i].size();j++)
         {
            int v = arr[i].get(j).val;
            int w = arr[i].get(j).color;
            if(w==0)
            {
              union(parent1,i,v,size1);
            }
         }
      }
      for(int i=1;i<=n;i++)
      {
         for(int j =0;j<arr[i].size();j++)
         {
            int v = arr[i].get(j).val;
            int w = arr[i].get(j).color;
            if(w==1)
            {
              union(parent2,i,v,size2);
            }
         }
      }

      long val =0;

      for(int i=1;i<=n;i++)
      {
        if(parent1[i]==i)
        {
            long val2 = size1[i];
           // out.println(val2);
            val = val + val2*(val2-1);
        }
      }
      for(int i=1;i<=n;i++)
      {
        if(parent2[i]==i)
        {
            long val2 = size2[i];
            val = val + val2*(val2-1);
        }
      }

      for(int i=1;i<=n;i++)
      {
        
            long val1 = size1[find(parent1,i)];
            long val2 = size2[find(parent2,i)];
            val = val + (val1-1)*(val2-1);
        
      }

      out.println(val);

    }
    public int find(int parent[], int u )
    {
        if(parent[u]==u)
            return u;

        parent[u]= find(parent,parent[u]);
        return parent[u];
    }   
    public void union(int parent[] , int u , int v , int size[])
    {

        int par1 = find(parent,u);
        int par2 = find(parent,v);
        if(par1!=par2)
        {
         parent[par1]=par2;
         size[par2]+= size[par1];
        }
    }
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int val ;
    int color;
    
    edge(int u, int v)
    {
       this.val=u;
       this.color=v;
    }
    public int compareTo(edge e)
    {
        return this.val-e.val;
    }
}