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.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class CF_1156D {

    static ArrayList<ArrayList<int[]>> adj = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = new PrintStream(new BufferedOutputStream(System.out));

        int n = in.nextInt();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            int t = in.nextInt();

            adj.get(u).add(new int[]{v, t});
            adj.get(v).add(new int[]{u, t});
        }

        boolean[] v0 = new boolean[n];
        boolean[] v1 = new boolean[n];
        long[] s0 = new long[n];
        long[] s1 = new long[n];

        long ret = 0;
        for (int i = 0; i < n; i++) {
            int size = sizeDFS(i, -1, 0, v0);

            if (size != -1 && size != 1) ret += 1L * size * size;
            fill(i, -1, 0, size, s0);

            size = sizeDFS(i, -1, 1, v1);
            if (size != -1 && size != 1) ret += 1L * size * size;

            fill(i, -1, 1, size, s1);
        }


        for (int i = 0; i < n; i++) {
            ret += Math.max((s0[i] - 1) * (s1[i] - 1) - 1, 0);
        }

        ret -= n;

        out.println(ret);


        out.close();
        in.close();
    }

    static int sizeDFS(int curr, int p, int t, boolean[] v) {
        if (v[curr]) return -1;
        v[curr] = true;

        int ret = 1;
        for (int[] u : adj.get(curr)) {
            if (u[0] != p && u[1] == t) {
                ret += sizeDFS(u[0], curr, t, v);
            }
        }
        return ret;
    }

    static void fill(int curr, int p, int t, int size, long[] sizes) {
        if (size == -1) return;

        sizes[curr] = size;
        for (int[] u : adj.get(curr)) {
            if (u[0] != p && u[1] == t) {
                fill(u[0], curr, t, size, sizes);
            }
        }
    }
}
