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.util.*;
import java.io.*;
public class D64
{
    static ArrayList<Edge> [] adj; static boolean [] visited; static Set<Integer> touched; static boolean inDFS;
    public static void main(String [] args)
    {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt();
        adj = new ArrayList[n+1]; UF ones = new UF(n+1); UF zeros = new UF(n+1);
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt(); int b = sc.nextInt(); int type = sc.nextInt();
            adj[a].add(new Edge(b, type)); adj[b].add(new Edge(a, type));
            if (type == 0) zeros.union(a, b); else ones.union(a, b);
        }
        long ans = 0; Set<Integer> processed = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            int par = ones.find(i);
            if (processed.contains(par)) continue;
            ans += ((long) ones.size[par] * (ones.size[par] - 1));
            processed.add(par);
        }
        processed = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            int par = zeros.find(i);
            if (processed.contains(par)) continue;
            ans += ((long) zeros.size[par] * (zeros.size[par] - 1));
            processed.add(par);
        }
        visited = new boolean[n+1]; int [] tree = new int[n+1]; touched = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            if (visited[i]) {
                int par = ones.find(i);
                int sz = ones.size[par];
                ans += ((long)(tree[i] - 1) * (sz - 1));
            } else {
                touched.add(i); int res = dfs(i);
                if (res != -1) {
                    for (Integer p: touched) {
                        tree[p] = res;
                    }
                    int par = ones.find(i);
                    int sz = ones.size[par];
                    ans += ((long)(tree[i] - 1) * (sz - 1));
                }
                touched = new HashSet<>(); inDFS = false;
            }
        }
        out.println(ans);

        out.close();
    }

    static int dfs(int cur) {
        Set<Integer> edges = new HashSet<>();
        for (Edge e: adj[cur]) edges.add(e.type);
        if (edges.size() == 1 && !inDFS) return -1; int ans = 1;
        inDFS = true;
        visited[cur] = true;
        for (Edge next: adj[cur]) {
            if (next.type == 0 && !visited[next.to]) {
                ans += dfs(next.to);
            } else if (next.type == 1) {
                touched.add(cur);
            }
        }
        return ans;
    }


    static class Edge {
        int to; int type;
        Edge(int to, int type) {
            this.to = to; this.type = type;
        }

    }

    static class UF {
        private int[] parent;  // parent[i] = parent of i
        private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
        private int count;     // number of components
        private int[] size;
        public UF(int n) {
            if (n < 0) throw new IllegalArgumentException();
            count = n;
            parent = new int[n];
            rank = new byte[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
                size[i] = 1;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];    // path compression by halving
                p = parent[p];
            }
            return p;
        }

        public int count() {
            return count;
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;

            // make root of smaller rank point to root of larger rank
            if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] = size[rootQ] + size[rootP];
            }
            else if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
                size[rootP] = size[rootP] + size[rootQ];
            }
            else {
                parent[rootQ] = rootP;
                size[rootP] = size[rootP] + size[rootQ];
                rank[rootP]++;
            }
            count--;
        }
    }



    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            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;
        }



    }

}