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 Main {
     static ArrayList a[]=new ArrayList[3000001];
     static ArrayList b[]=new ArrayList[3000001];
     static boolean visited[]=new boolean [3000001];
     static long dp[][]=new long[300001][2];
     static int p[]=new int[300001];
     static Vector<Integer>color=new Vector<>();
     static void dfs(int n) {
    	 color.add(n);
    	 visited[n]=true;
    	 for(int i=0;i<b[n].size();i++) {
    		int id=(int)b[n].get(i);
    		 if(!visited [id]) {
    			 dfs(id);
    		 }
    	 }
     }
     static void dfs1(int n) {
    	 color.add(n);
    	 visited[n]=true;
    	 for(int i=0;i<a[n].size();i++) {
    		int id=(int)a[n].get(i);
    		 if(!visited [id]) {
    			 dfs1(id);
    		 }
    	 }
     }
     
     public static void main(String[]args)
    {
        InputReader in=new InputReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n=in.nextInt();
        for(int i=0;i<=n;i++) {
        	a[i]=new ArrayList<Integer>();
        	b[i]=new ArrayList<Integer>();
        }
        for(int i=0;i<n-1;i++) {
        	int x=in.nextInt();
        	int y=in.nextInt();
        	int c=in.nextInt();
            if(c==1) {
            	b[x].add(y);
            	b[y].add(x);
            }
            else
            {
            	a[x].add(y);
            	a[y].add(x);
            }
        }
        int parent=1;
        for(int i=1;i<=n;i++) {
        	
        	
        	if(!visited[i])
        	{	
        		dfs(i);	
         		if(color.size()==1)
        		{
            		color.clear();
        			continue;
        		}
        		for(int j=0;j<color.size();j++) {
        			int got=color.get(j);
        			p[got]=parent;
        			dp[got][1]=color.size()-1;
        		}
        		parent++;
        		color.clear();
        	}
        }
        Arrays.fill(visited, false);
        for(int i=1;i<=n;i++) {
        	if(!visited[i]) {
        		dfs1(i);	
        		if(color.size()==1)
        		{
            		color.clear();
        			continue;
        		}
        		long ans=0;
        		TreeSet<Integer>tr=new TreeSet<>();
        		for(int j=0;j<color.size();j++) {
        			int got=color.get(j);
        			for(int k=0;k<b[got].size();k++) {
        				int idx=(int) b[got].get(k);
        				if(!tr.contains(p[idx])) {
        					ans+=dp[idx][1];
        					tr.add(p[idx]);
        				}
        			}
        		}
        		for(int j=0;j<color.size();j++) {
        			int got=color.get(j);
        			dp[got][0]=color.size()-1+ans-dp[got][1];
        		}
        		color.clear();
        	}
        
        }
        long ans=0;
        for(int i=1;i<=n;i++) {
        	ans+=dp[i][0];
        	ans+=dp[i][1];
        }
        pw.println(ans);
        pw.flush();
        pw.close();
 
    }
    private static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
   static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        { 
            this.stream = stream;
        }
        public int snext() 
        {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() 
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
        static class tri implements Comparable<tri> {
            int p, c, l;
 
            tri(int p, int c, int l) {
                this.p = p;
                this.c = c;
                this.l = l;
            }
 
            public int compareTo(tri o) {
                return Integer.compare(l, o.l);
            }
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
   public static long modularExponentiation(long x,long n,long M)
   {
       long result=1;
       while(n>0)
       {
           if(n % 2 ==1)
               result=(result%M * x%M)%M;
           x=(x%M * x%M)%M;
           n=n/2;
       }
       return result;
   }
   
   public static long modInverse(int A,int M)
   {
       return modularExponentiation(A,M-2,M);
   }
   
   public static long modInverse(long A,long M)
   {
       return modularExponentiation(A,M-2,M);
   }
   static class pair implements Comparable<pair>
   {
       Integer x, y;
       pair(int x,int y)
       {
           this.x=x;
           this.y=y;
       }

       public int compareTo(pair o) {
           int result = x.compareTo(o.x);
           if(result==0)
               result = y.compareTo(o.y);

           return result;
       }

       public String toString()
       {
           return x+" "+y;
       }

       public boolean equals(Object o)
       {
           if (o instanceof pair)
          {
               pair p = (pair)o;
               return (Math.abs(p.x-x)==0 && Math.abs(p.y-y)==0);
           }
           return false;
       }

       public int hashCode()
       {
           return new Long(x).hashCode()*31 + new Long(y).hashCode();
       }
   }
    public static long GCD(long a,long b)
    {
        if(b==0)
            return a;
        else
            return GCD(b,a%b);
    }
    public static long[] shuffle(long[] a, Random gen){ 
        for(int i = 0, n = a.length;i < n;i++){ 
            int ind = gen.nextInt(n-i)+i; 
            long d = a[i]; 
            a[i] = a[ind]; 
            a[ind] = d; 
        } 
        return a; 
    }
  
    
}