1156_D. 0-1-Tree_28542
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>
# Test without fastIO
# With fastIO it takes 326 ms

class mergefind:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n

    def find(self,a):
        to_update = []
       
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
       
        for b in to_update:
            self.parent[b] = a

        return self.parent[a]

    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)

        if a==b:
            return

        if self.size[a]<self.size[b]:
            a,b = b,a

        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


def main():
    n = int(input())

    dsu = mergefind(n)

    inp = [int(x) for _ in range(n-1) for x in input().split()]
    
    ii = 0
    for _ in range(n-1):
        u,v,c = inp[ii]-1,inp[ii+1]-1,inp[ii+2]
        ii += 3
        
        if c==1:
            dsu.merge(u,v)
    
    dsu2 = mergefind(n)
    for i in range(n):
        dsu2.size[i] = dsu.size[dsu.find(i)]

    ii = 0
    for _ in range(n-1):
        u,v,c = inp[ii]-1,inp[ii+1]-1,inp[ii+2]
        ii += 3
        
        if c==0:
            dsu2.merge(u,v)

    pairs = 0
    for i in range(n):
        i = dsu2.find(i)
        pairs += dsu2.size[i]-1
    print pairs




######## Python 2 and 3 footer by Pajenegod and c1729 

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
    from cStringIO import StringIO as BytesIO
    input = raw_input
else:
    from io import BytesIO
    __str__ = str
    str = lambda x=b'': x if type(x) is bytes else __str__(x).encode()

if __name__== "__main__":
  main()
7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1
 2
1 2 1
 2
1 2 0
 7
2 1 1
3 2 0
4 2 1
5 4 0
6 7 1
7 2 1
 7
2 1 1
3 2 1
4 2 1
5 2 0
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 0
7 2 1
 7
3 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 2 1
5 2 0
6 5 0
7 2 1
 7
2 1 1
3 2 0
4 1 1
5 2 0
6 7 1
7 2 1
 7
2 1 0
3 2 1
4 1 1
5 2 0
6 7 0
7 2 1
 7
2 1 1
3 1 1
4 1 1
5 2 1
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 3 1
5 2 1
6 7 0
7 2 1
 7
2 1 1
3 1 0
4 1 1
5 2 0
6 7 0
7 2 1
 7
2 1 0
3 6 1
4 1 0
5 2 0
6 7 0
7 1 1
 7
2 1 1
3 2 0
4 2 1
5 1 0
6 7 1
7 2 1
 7
2 1 1
3 2 1
4 1 1
5 2 0
6 7 1
7 2 1
 7
2 1 1
3 2 1
4 1 1
5 2 0
6 7 0
7 2 1
 7
2 1 1
3 1 1
4 1 1
5 2 0
6 7 0
7 2 1
 7
2 1 1
3 2 0
4 2 0
5 1 0
6 7 1
7 2 1
 7
2 1 1
3 1 1
4 1 1
5 2 1
6 7 0
7 2 1
 7
2 1 0
3 2 1
4 1 0
5 2 0
6 7 0
7 2 1
 7
2 1 1
3 2 0
4 2 1
5 2 1
6 7 0
7 2 1
 7
2 1 1
3 2 0
4 1 1
5 2 0
6 7 0
7 2 1
 7
4 1 1
3 2 0
4 2 1
5 4 0
6 7 1
7 2 1
 7
4 1 1
3 2 1
4 2 1
5 4 0
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 3 1
5 2 1
6 7 0
7 2 0
 7
4 1 1
3 2 1
4 2 1
5 4 0
6 7 1
7 4 1
 7
4 1 1
3 2 1
4 2 1
5 7 0
6 7 1
7 4 1
 7
2 1 1
3 2 0
4 2 1
5 4 0
6 7 1
7 4 1
 7
2 1 1
3 1 0
4 2 1
5 2 0
6 7 0
7 2 1
 7
2 1 1
3 2 1
4 1 1
5 4 0
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 2 1
5 3 0
6 5 0
7 2 1
 7
2 1 1
3 2 1
4 1 1
5 2 1
6 7 0
7 2 1
 7
2 1 0
3 2 1
4 1 0
5 2 0
6 7 0
7 3 1
 7
2 1 1
3 1 1
4 2 1
5 2 1
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 2 1
5 4 0
6 7 1
7 1 1
 7
2 1 1
3 1 0
4 2 1
5 2 0
6 7 1
7 2 1
 7
2 1 0
3 2 1
4 1 0
5 2 0
6 7 0
7 3 0
 7
2 1 1
3 2 0
4 1 1
5 4 0
6 7 1
7 1 1
 7
2 1 0
3 2 1
4 1 0
5 2 0
6 7 0
7 1 0
 7
2 1 0
3 2 1
4 1 0
5 2 0
6 7 0
7 1 1
 7
2 1 0
3 4 1
4 1 0
5 2 0
6 7 0
7 1 1
 7
2 1 0
3 6 1
4 1 0
5 1 0
6 7 0
7 1 1
 7
2 1 1
3 2 0
4 1 1
5 2 0
6 4 0
7 2 1
 7
4 1 1
3 4 0
4 2 1
5 4 0
6 7 1
7 2 1
 7
4 1 1
3 4 1
4 2 1
5 4 0
6 7 1
7 2 1
 7
2 1 1
3 2 1
4 3 1
5 2 1
6 7 0
7 2 0
 7
6 1 1
3 2 1
4 2 1
5 4 0
6 7 1
7 4 1
 7
2 1 1
3 1 0
4 2 1
5 2 1
6 7 0
7 2 1
 7
3 1 1
3 2 1
4 1 1
5 4 0
6 7 1
7 2 1
 7
2 1 0
3 4 1
4 1 0
5 2 0
6 7 0
7 3 1
 7
2 1 1
3 1 1
4 2 1
5 2 1
6 7 0
7 2 1
 7
2 1 1
3 1 0
4 2 0
5 2 0
6 7 1
7 2 1
 7
2 1 0
3 2 1
4 1 0
5 3 0
6 7 0
7 3 0
 7
2 1 1
3 2 0
4 1 1
5 1 0
6 7 1
7 1 1
 7
2 1 0
3 2 1
4 2 0
5 2 0
6 7 0
7 1 0
 7
2 1 1
3 2 0
4 1 1
5 2 0
6 4 0
7 3 1
 7
2 1 1
3 4 0
4 2 1
5 4 0
6 7 1
7 2 1
 7
2 1 1
3 1 0
4 2 1
5 2 1
6 7 0
6 2 1
 7
2 1 1
3 1 1
4 2 1
5 2 1
6 7 0
7 3 1
 7
2 1 1
3 2 1
4 2 1
5 3 0
6 7 1
7 2 1
 7
2 1 0
3 2 1
4 1 1
5 2 0
6 7 1
7 2 1
 7
3 1 1
3 2 1
4 2 1
5 2 0
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 3 1
5 2 0
6 5 0
7 2 1
 7
2 1 1
3 1 1
4 1 1
5 2 1
6 7 0
7 2 0
 7
2 1 0
3 2 0
4 1 0
5 2 0
6 7 0
7 2 1
 7
2 1 1
3 2 0
4 1 1
5 2 0
6 7 0
7 1 1
 7
2 1 1
3 1 1
4 1 1
5 1 1
6 7 1
7 2 1
 7
3 1 1
3 2 1
4 2 1
5 4 0
6 7 1
7 2 1
 7
2 1 1
3 2 0
4 3 1
5 3 1
6 7 0
7 2 0
 7
4 1 1
3 2 1
4 2 1
5 4 1
6 7 1
7 4 1
 7
2 1 1
3 4 0
4 2 1
5 4 0
6 7 1
7 4 1
 7
2 1 1
3 2 0
4 1 1
5 2 1
6 7 0
7 2 1
 7
2 1 0
3 2 1
4 1 0
5 2 0
6 1 0
7 1 0

34
 2
 2
 32
 37
 29
 28
 33
 34
 24
 42
 25
 27
 23
 32
 37
 32
 32
 29
 37
 28
 32
 29
 32
 37
 29
 37
 37
 32
 27
 37
 33
 37
 28
 42
 32
 32
 25
 32
 37
 25
 25
 23
 29
 34
 37
 34
 37
 32
 37
 28
 37
 29
 25
 32
 37
 24
 34
 32
 37
 37
 28
 37
 29
 34
 29
 29
 42
 37
 29
 42
 34
 32
 37
