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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class TaskD {
        List<Edge>[] g;
        long[] r0;
        long[] r1;
        long[] r01;
        long[] r10;
        long ans = 0;

        void dfs(int v, int p) {
//        long prev0 = 0;
//        long prev1 = 0;
//        long prev01 = 0;
//        long prev10 = 0;
            for (Edge edge : g[v]) {
                if (edge.to != p) {
                    dfs(edge.to, v);
                    if (edge.c == 0) {
                        ans += (1 + r0[edge.to]) * (2 * r0[v] + r01[v]) + (r01[edge.to] + r1[edge.to]) * r0[v];
                        ans += (1 + r0[edge.to]) * r1[v];
                        r0[v] += 1 + r0[edge.to];
                        r01[v] += r01[edge.to] + r1[edge.to];

//                    prev0 += r0[edge.to];
//                    prev01 += r01[edge.to]+r1[edge.to];
                    } else {
                        ans += (1 + r1[edge.to]) * (2 * r1[v] + r10[v]) + (r10[edge.to] + r0[edge.to]) * r1[v];
                        ans += (1 + r1[edge.to]) * r0[v];
                        r1[v] += 1 + r1[edge.to];
                        r10[v] += r10[edge.to] + r0[edge.to];

//                    prev1 += r1[edge.to];
//                    prev10 += r10[edge.to]+r0[edge.to];
                    }
                }
            }
            ans += 2 * r0[v] + 2 * r1[v] + r01[v] + r10[v];
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int N = in.ni();
            g = new List[N];
            r0 = new long[N];
            r1 = new long[N];
            r01 = new long[N];
            r10 = new long[N];
            for (int i = 0; i < N; i++) {
                g[i] = new LinkedList<>();
            }
            for (int i = 0; i < N - 1; i++) {
                int from = in.ni() - 1, to = in.ni() - 1, c = in.ni();
                g[from].add(new Edge(from, to, c));
                g[to].add(new Edge(to, from, c));
            }
            dfs(0, -1);
            out.println(ans);
        }

        class Edge {
            int from;
            int to;
            int c;

            public Edge(int from, int to, int c) {
                this.from = from;
                this.to = to;
                this.c = c;
            }

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

    }
}

