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.Vector;
import java.util.TreeMap;
import java.util.Scanner;
import java.util.LinkedList;
import java.util.TreeSet;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        OutputStream outputStream = System.out;
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public int N = 200005;
        public Vector<Integer> g0[] = new Vector[N];
        public Vector<Integer> g1[] = new Vector[N];
        public int color[] = new int[N];
        public int component[] = new int[N];
        public boolean visited2[] = new boolean[N];

        int dfs(int node, int c) {
            int ret = 1;
            color[node] = c;
            for (Integer newNode : g1[node]) {
                if (color[newNode] != c)
                    ret += dfs(newNode, c);
            }
            return ret;
        }

        long solveZero(int node, PrintWriter out) {
            long ret = 0;
            TreeMap<Integer, Integer> takenComponents = new TreeMap<>();
            long minus = 0;
            LinkedList<Integer> que = new LinkedList<Integer>();
            visited2[node] = true;
            que.addFirst(node);
            int size = 0;
            while (que.size() > 0) {
                int curNode = que.peekFirst();
                que.removeFirst();
                size++;
                TreeSet<Integer> connectedTo = new TreeSet<Integer>();
                for (Integer con : g1[curNode]) {
                    connectedTo.add(color[con]);
                }
                for (Integer con : connectedTo) {
                    if (takenComponents.containsKey(con) == true)
                        takenComponents.put(con, takenComponents.get(con) + 1);
                    else
                        takenComponents.put(con, 1);
                }
                for (Integer con : g0[curNode]) {
                    if (!visited2[con]) {
                        visited2[con] = true;
                        que.addFirst(con);
                    }
                }
            }
            long plus = 0;
            for (Integer con : takenComponents.keySet()) {
                minus += (component[con] - takenComponents.get(con)) * takenComponents.get(con);
                plus += component[con] - takenComponents.get(con);
            }
            return size * (size + plus - 1) - minus;
        }

        public void solve(int testNumber, FastReader in, PrintWriter out) {
            for (int i = 0; i < N; i++) {
                g0[i] = new Vector<Integer>();
                g1[i] = new Vector<Integer>();
            }
            int n = in.nextInt();
            for (int i = 0; i < n - 1; i++) {
                int u, v, t;
                u = in.nextInt();
                v = in.nextInt();
                t = in.nextInt();
                u--;
                v--;
                if (t == 1) {
                    g1[u].add(v);
                    g1[v].add(u);
                } else {
                    g0[u].add(v);
                    g0[v].add(u);
                }
            }
            long ans = 0;
            int c = 1;
            for (int i = 0; i < n; i++) {
                if (color[i] == 0) {
                    int cur = dfs(i, c);
                    component[c++] = cur;
                    ans += (long) cur * (cur - 1);
                }
            }
            for (int i = 0; i < n; i++) {
                if (!visited2[i]) {
                    ans += solveZero(i, out);
                }
            }
            out.print(ans);
        }

    }

    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}

