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 ZeroOneTree {
    public static Node[] nodes;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(f.readLine());
        nodes = new Node[n+1];
        LinkedList<Edge>[] edges = new LinkedList[n+1];
        for(int i = 0; i <= n; i++){
            nodes[i] = new Node(i);
        }
        for(int i = 0; i <= n; i++){
            edges[i] = new LinkedList<Edge>();
        }
        for(int i = 0; i < n-1; i++){
            StringTokenizer st = new StringTokenizer(f.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edges[a].add(new Edge(b, c));
            edges[b].add(new Edge(a, c));
        }
        HashSet<Integer> visited = new HashSet<Integer>();
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.add(1);
        while(!q.isEmpty()){
            int temp = q.poll();
            if(visited.contains(temp)) continue;
            visited.add(temp);
            for(Edge e: edges[temp]){
                if(!visited.contains(e.dest)){
                    nodes[temp].children.add(new Edge(e.dest, e.val));
                    q.add(e.dest);
                }
            }
        }
        ArrayList<Integer> postorder = postorder(nodes[1]);
        for(int nid: postorder){
            if(nodes[nid].children.size() == 0) nodes[nid].sum = 0;
            for(int i = 0; i < nodes[nid].children.size(); i++){
                nodes[nid].sum += nodes[nodes[nid].children.get(i).dest].sum;
                if(nodes[nid].children.get(i).val == 0){
                    nodes[nid].onezero += nodes[nodes[nid].children.get(i).dest].one;
                    nodes[nid].onezero += nodes[nodes[nid].children.get(i).dest].onezero;
                    nodes[nid].zero += nodes[nodes[nid].children.get(i).dest].zero+1;
                    nodes[nodes[nid].children.get(i).dest].onezero += nodes[nodes[nid].children.get(i).dest].one;
                    nodes[nodes[nid].children.get(i).dest].one = 0;
                    nodes[nodes[nid].children.get(i).dest].zeroone = 0;
                    nodes[nodes[nid].children.get(i).dest].zero += 1;
                }else{
                    nodes[nid].zeroone += nodes[nodes[nid].children.get(i).dest].zero;
                    nodes[nid].zeroone += nodes[nodes[nid].children.get(i).dest].zeroone;
                    nodes[nid].one += nodes[nodes[nid].children.get(i).dest].one+1;
                    nodes[nodes[nid].children.get(i).dest].zeroone += nodes[nodes[nid].children.get(i).dest].zero;
                    nodes[nodes[nid].children.get(i).dest].zero = 0;
                    nodes[nodes[nid].children.get(i).dest].onezero = 0;
                    nodes[nodes[nid].children.get(i).dest].one += 1;
                }
            }
            nodes[nid].sum += 2*nodes[nid].zero;
            nodes[nid].sum += 2*nodes[nid].one;
            nodes[nid].sum += nodes[nid].zeroone;
            nodes[nid].sum += nodes[nid].onezero;

            for(int i = 1; i < nodes[nid].children.size(); i++){
                nodes[nid].sum += 2*nodes[nodes[nid].children.get(0).dest].zero*nodes[nodes[nid].children.get(i).dest].zero;
                nodes[nid].sum += 2*nodes[nodes[nid].children.get(0).dest].one*nodes[nodes[nid].children.get(i).dest].one;
                nodes[nid].sum += nodes[nodes[nid].children.get(0).dest].zero*nodes[nodes[nid].children.get(i).dest].one;
                nodes[nid].sum += nodes[nodes[nid].children.get(0).dest].one*nodes[nodes[nid].children.get(i).dest].zero;
                nodes[nid].sum += nodes[nodes[nid].children.get(0).dest].zeroone*nodes[nodes[nid].children.get(i).dest].one;
                nodes[nid].sum += nodes[nodes[nid].children.get(0).dest].one*nodes[nodes[nid].children.get(i).dest].zeroone;
                nodes[nid].sum += nodes[nodes[nid].children.get(0).dest].onezero*nodes[nodes[nid].children.get(i).dest].zero;
                nodes[nid].sum += nodes[nodes[nid].children.get(0).dest].zero*nodes[nodes[nid].children.get(i).dest].onezero;
                nodes[nodes[nid].children.get(0).dest].zero += nodes[nodes[nid].children.get(i).dest].zero;
                nodes[nodes[nid].children.get(0).dest].one += nodes[nodes[nid].children.get(i).dest].one;
                nodes[nodes[nid].children.get(0).dest].zeroone += nodes[nodes[nid].children.get(i).dest].zeroone;
                nodes[nodes[nid].children.get(0).dest].onezero += nodes[nodes[nid].children.get(i).dest].onezero;
            }
        }
        out.println(nodes[1].sum);
        out.close();

    }

    static class Pair {
        public Node node;
        public int childrenIndex;
        public Pair(Node _node, int _childrenIndex)
        {
            node = _node;
            childrenIndex = _childrenIndex;
        }
    }

    // We will keep the start index as 0,
    // because first we always
    // process the left most children
    public static int currentRootIndex = 0;
    public static Stack<Pair> stack = new Stack<Pair>();
    public static ArrayList<Integer> postorderTraversal =
            new ArrayList<Integer>();

    // Function to perform iterative postorder traversal
    public static ArrayList<Integer> postorder(Node root)
    {
        while (root != null || !stack.isEmpty()) {
            if (root != null) {

                // Push the root and it's index
                // into the stack
                stack.push(new Pair(root, currentRootIndex));
                currentRootIndex = 0;

                // If root don't have any children's that
                // means we are already at the left most
                // node, so we will mark root as null
                if (root.children.size() >= 1) {
                    root = nodes[root.children.get(0).dest];
                }
                else {
                    root = null;
                }
                continue;
            }

            // We will pop the top of the stack and
            // add it to our answer
            Pair temp = stack.pop();
            postorderTraversal.add(temp.node.id);

            // Repeatedly we will the pop all the
            // elements from the stack till popped
            // element is last children of top of
            // the stack
            while (!stack.isEmpty() && temp.childrenIndex ==
                    stack.peek().node.children.size() - 1) {
                temp = stack.pop();

                postorderTraversal.add(temp.node.id);
            }

            // If stack is not empty, then simply assign
            // the root to the next children of top
            // of stack's node
            if (!stack.isEmpty()) {
                root = nodes[stack.peek().node.children.get(temp.childrenIndex + 1).dest];
                currentRootIndex = temp.childrenIndex + 1;
            }
        }

        return postorderTraversal;
    }


    static class Node{
        public int id;
        public ArrayList<Edge> children;
        public long sum;
        public long zero;
        public long one;
        public long zeroone;
        public long onezero;

        public Node(int i){
            id = i;
            children = new ArrayList<Edge>();
            sum = 0;
            zero = 0;
            one = 0;
            zeroone = 0;
            onezero = 0;
        }
    }
    static class Edge{
        public int dest;
        public int val;

        public Edge(int d, int v){
            dest = d;
            val = v;
        }
    }
}

