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 Main
{
    int refID = 0 ;
    long ans = 0 ;
    boolean [] taken ;
    int [] head , next , size ;
    long [] tot , curr;
    Edge [] to ;
    int [][] nextMasks = {{0 , 1 , 3} , {0} , {3} , {0 , 2 , 3}};

    void addEdge(int a , int b , int c)
    {
        next[++refID] = head[a] ;
        head[a] = refID ;
        to[refID] = new Edge(b , c) ;
    }

    int getSize(int u , int p)
    {
        int sz = 1;
        for(int i = head[u] ; i != 0 ; i = next[i])
        {
            Edge e = to[i] ;
            int v = e.v ;
            if(v != p && !taken[v])
                sz += getSize(v , u) ;
        }
        return size[u] = sz ;
    }
    int getCentroid(int u , int p , int n)
    {
        for(int i = head[u] ; i != 0 ; i = next[i])
        {
            Edge e = to[i] ;
            int v = e.v ;
            if(v != p && !taken[v] && size[v] * 2 > n)
                return getCentroid(v , u , n) ;
        }
        return u ;
    }
    boolean isValid(int start , int end , int current)
    {
        return !(start != end && start == current) ;
    }
    void compute(int u , int p , int start , int end)
    {
        ans += (start == end) ? 2 : 1;
        curr[start << 1 | end] ++ ;
        for(int mask : nextMasks[start << 1 | end])
            ans += tot[mask] * (((mask == (start << 1 | end))) ? 2 : 1) ;

        for(int i = head[u] ; i != 0 ; i = next[i])
        {
            Edge e = to[i] ;
            int v = e.v ;
            if(v != p && !taken[v])
                if(isValid(start , end , e.w))
                    compute(v , u , start , e.w);
        }
    }
    void decompose(int u)
    {
        int sz = getSize(u, -1);
        int centroid = getCentroid(u, -1, sz);
        tot = new long[4];
        curr = new long[4];
        taken[centroid] = true;
        for (int i = head[centroid]; i != 0; i = next[i]) {
            Edge e = to[i];
            if (!taken[e.v])
            {
                compute(e.v, centroid, e.w, e.w);
                for (int j = 0; j < 4; j++)
                {
                    tot[j] += curr[j];
                    curr[j] = 0 ;
                }
            }
        }
        for (int i = head[centroid]; i != 0; i = next[i])
        {
            Edge e = to[i];
            if (!taken[e.v])
                decompose(e.v);
        }
    }

    void solve() throws Exception
    {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt() ;
        next = new int[n << 1] ;
        head = new int [n] ;
        to = new Edge[n << 1] ;
        size = new int [n] ;
        taken = new boolean[n] ;
        for(int i = 0 ; i < n - 1 ; i ++)
        {
            int u = sc.nextInt() - 1 , v = sc.nextInt() - 1 , w = sc.nextInt() ;
            addEdge(u , v , w); addEdge(v , u , w);
        }
        decompose(0);
        out.println(ans);
        out.close();

    }
    class Edge
    {
        int v , w ;
        Edge(int b , int c){ v = b ; w = c;}
    }
    public static void main (String [] args) throws Exception { new Main().solve(); }

    class Scanner
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException { return Integer.parseInt(next()); }
    }
}