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>
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1156D
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         LinkedList<Edge>[] edges = new LinkedList[N+1];
         for(int i=1; i <= N; i++)
            edges[i] = new LinkedList<Edge>();
         for(int i=1; i < N; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[a].add(new Edge(b,c));
            edges[b].add(new Edge(a,c));
         }
         int root = 1;
         long[][] dp = new long[N+1][2];
         dfs(root, dp, new boolean[N+1], edges);
         //dp[i][0] = # of children to i paths that end with 0
         //dp[i][1] = # of children to i paths containing 1
         
         long[][] dp2 = new long[N+1][2];
         //dp2[i][0/1] = # of paths ending at i
         reroot(root, dp2, new boolean[N+1], edges, dp);
         long res = 0L;
         for(int i=1; i <= N; i++)
            res += dp2[i][0]+dp2[i][1];
            
         System.out.println(res);
      }
      public static void reroot(int curr, long[][] dp, boolean[] seen, LinkedList<Edge>[] edges, long[][] dp_subtree)
      {
         seen[curr] = true;
         dp[curr][0] += dp_subtree[curr][0];
         dp[curr][1] += dp_subtree[curr][1];
         for(Edge e: edges[curr])
         {
            int next = e.to;
            if(seen[next])
               continue;
            if(e.color == 0)
            {
               long prev = dp[curr][0];
               prev -= dp_subtree[next][0];
               dp[next][0] += prev;
            }
            else
            {
               long prev = dp[curr][1]+dp[curr][0];
               prev -= dp_subtree[next][0]+dp_subtree[next][1];
               dp[next][1] += prev;
            }
            reroot(next, dp, seen, edges, dp_subtree);
         }
      }
      public static void dfs(int curr, long[][] dp, boolean[] seen, LinkedList<Edge>[] edges)
      {
         seen[curr] = true;
         long res0 = 0L;
         long res1 = 0L;
         for(Edge e: edges[curr])
         {
            int next = e.to;
            if(seen[next])
               continue;
            dfs(next, dp, seen, edges);
            if(e.color == 0)
               res0 += 1+dp[next][0];
            else
               res1 += 1+dp[next][0]+dp[next][1];
         }
         dp[curr][0] += res0;
         dp[curr][1] += res1;
      }
   }
   class Edge
   {
      public int to;
      public int color;
      
      public Edge(int a, int b)
      {
         to = a;
         color = b;
      }
   }