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>
//make sure to make new file!
import java.io.*;
import java.util.*;

public class D1156{

   public static ArrayList<ArrayList<Edge>> adj;
   public static long[][] sub;
   public static long[][] dp;
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      adj = new ArrayList<ArrayList<Edge>>(n+1);
      
      for(int k = 0; k <= n; k++) adj.add(new ArrayList<Edge>());
      
      for(int k = 0; k < n-1; k++){
         StringTokenizer st = new StringTokenizer(f.readLine());
         int a = Integer.parseInt(st.nextToken());
         int b = Integer.parseInt(st.nextToken());
         int c = Integer.parseInt(st.nextToken());
         
         adj.get(a).add(new Edge(b,c));
         adj.get(b).add(new Edge(a,c));
      }
      
      
      sub = new long[n+1][2];                          //[node][0 or 1];
      dp = new long[n+1][2];
      
      
      subdfs(1,-1);
      
      dpdfs(1,-1);
      
      long answer = 0L;
      for(int k = 1; k <= n; k++){
         for(int j = 0; j <= 1; j++){
            answer+=dp[k][j];
         }
      }
      
      out.println(answer);
      
      out.close();
   }
   
   public static void dpdfs(int v, int p){
      dp[v][0] += sub[v][0];
      dp[v][1] += sub[v][1];
      
      for(Edge e : adj.get(v)){
         if(e.nei == p) continue;
         if(e.w == 0){
            dp[e.nei][0] = dp[v][0] + dp[v][1] - sub[e.nei][0] - sub[e.nei][1];
         } else {
            dp[e.nei][1] = dp[v][1] - sub[e.nei][1];
         }
         dpdfs(e.nei,v);
      }
   }
   
   public static void subdfs(int v, int p){
      
      sub[v][0] = 0L;
      sub[v][1] = 0L;
      
      for(Edge e : adj.get(v)){
         if(e.nei == p) continue;
         subdfs(e.nei,v);
         if(e.w == 0){
            sub[v][0] += sub[e.nei][0] + sub[e.nei][1] + 1;     
         } else {
            sub[v][1] += sub[e.nei][1] + 1;
         }
      }
   }
   
   
   public static class Edge{
      int nei;
      int w;
      public Edge(int a, int b){
         nei = a;
         w = b;
      }
   }
   
      
}