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 sys

class Disjoint:
    def __init__(self, n):
        self.n = n
        self.size = [1] * self.n
        self.parent = [i for i in range(self.n)]
    
    def root(self, node):
        self.parent[node] = node if self.parent[node] == node else self.root(self.parent[node])
        return self.parent[node]
    
    def join(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return False
        if self.size[a] > self.size[b]:
            a, b = b, a
            
        self.size[b] += self.size[a]
        self.parent[a] = b
        return True
    
    

inp = [int(x) for x in sys.stdin.read().split()]
n = inp[0]

white = Disjoint(n)
black = Disjoint(n)

inp_idx = 1
for i in range(n - 1):
    x, y, c = inp[inp_idx], inp[inp_idx + 1], inp[inp_idx + 2]
    x -= 1
    y -= 1
    inp_idx += 3
    
    if c == 0:
        white.join(x, y)
    else:
        black.join(x, y)
    
ans = 0
for i in range(n):
    rootW = white.root(i)
    rootB = black.root(i)
    ans += white.size[rootW] - 1
    ans += black.size[rootB] - 1
    
    ans += (white.size[rootW] - 1) * (black.size[rootB] - 1)
    
print(ans)
        