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
from array import array  # noqa: F401
import typing as Tp  # noqa: F401


def input():
    return sys.stdin.buffer.readline().decode('utf-8')


class UnionFind(object):
    __slots__ = ['nodes']

    def __init__(self, n: int):
        self.nodes = [-1] * n

    def size(self, x: int) -> int:
        return -self.nodes[self.find(x)]

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y, nodes = self.find(x), self.find(y), self.nodes

        if root_x != root_y:
            if nodes[root_x] > nodes[root_y]:
                root_x, root_y = root_y, root_x
            nodes[root_x] += nodes[root_y]
            nodes[root_y] = root_x

        return root_x != root_y


def main():
    n = int(input())
    adj = [[] for _ in range(n)]
    union0, union1 = UnionFind(n), UnionFind(n)

    for u, v, c in (map(int, input().split()) for _ in range(n - 1)):
        adj[u - 1].append((v - 1, c))
        adj[v - 1].append((u - 1, c))
        if c == 0:
            union0.unite(u - 1, v - 1)
        else:
            union1.unite(u - 1, v - 1)

    ans = 0

    for i in range(n):
        size0, size1 = union0.size(i), union1.size(i)

        if union0.find(i) == i:
            ans += size0 * (size0 - 1)
        if union1.find(i) == i:
            ans += size1 * (size1 - 1)

        ans += (size0 - 1) * (size1 - 1)

    print(ans)


if __name__ == '__main__':
    main()
