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 collections import deque

sys.setrecursionlimit(10 ** 9)


def get(dtype=int):
    return dtype(raw_input())


def array(dtype=int):
    return [dtype(num) for num in raw_input().split()]


n = get()

G = [[] for _ in range(n)]

P = [-1 for _ in range(n)]

for i in range(n - 1):
    u, v, z = array()

    u -= 1
    v -= 1

    G[u].append((v, z))
    G[v].append((u, z))

pu = [[0 for _ in range(n)] for j in range(2)]
pd = [[0 for _ in range(n)] for j in range(2)]


def dfs_compute(i, p):
    global total_paths
    extras = 0
    for j, e in G[i]:
        if j == p:
            continue
        dfs_compute(j, i)

        if e == 0:
            pu[0][i] += pu[0][j] + 1
            pd[0][i] += pd[0][j] + pd[1][j] + 1
            extras += (pu[0][j] + 1) * (pd[0][j] + pd[1][j] + 1)
        else:
            pu[1][i] += pu[0][j] + pu[1][j] + 1
            pd[1][i] += pd[1][j] + 1
            extras += (pu[0][j] + pu[1][j] + 1) * (pd[1][j] + 1)

    bends = pu[0][i] * pd[0][i] + pu[0][i] * pd[1][i] + pu[1][i] * pd[1][i]
    straights = pu[0][i] + pu[1][i] + pd[0][i] + pd[1][i]
    paths = bends + straights - extras

    total_paths += paths

    # print '[', i, ']:', pu[0][i], pu[1][i], pd[0][i], pd[1][i], bends, straights, extras, paths


total_paths = 0
# dfs_compute(0, -1)
q = deque([[0, 0, -1]])

while q:
    x, i, p = q.pop()
    # print x, i, p
    if x == 0:
        q.append([1, i, p])
        for j, e in G[i]:
            if j == p:
                continue
            q.append([0, j, i])

    elif x == 1:
        extras = 0
        for j, e in G[i]:
            if j == p:
                continue
            if e == 0:
                pu[0][i] += pu[0][j] + 1
                pd[0][i] += pd[0][j] + pd[1][j] + 1
                extras += (pu[0][j] + 1) * (pd[0][j] + pd[1][j] + 1)
            else:
                pu[1][i] += pu[0][j] + pu[1][j] + 1
                pd[1][i] += pd[1][j] + 1
                extras += (pu[0][j] + pu[1][j] + 1) * (pd[1][j] + 1)

        bends = pu[0][i] * pd[0][i] + pu[0][i] * pd[1][i] + pu[1][i] * pd[1][i]
        straights = pu[0][i] + pu[1][i] + pd[0][i] + pd[1][i]
        paths = bends + straights - extras

        total_paths += paths

print total_paths
