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>
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    la0 = [None] * (n + 1)
    xt0 = [None] * (3 * n - 3)
    la1 = [None] * (n + 1)
    xt1 = [None] * (3 * n - 3)
    j = 0
    for i in xrange(n - 1):
        x, y, z = dat[i*3:i*3+3]
        la = la1 if z else la0
        xt = xt1 if z else xt0
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 2
    cnt = [0] * (n + 1)
    st = []
    po = st.pop
    pu = st.append
    t = []
    put = t.append
    ans = 0
    for i in xrange(1, n + 1):
        if cnt[i]:
            continue
        pu(i)
        cnt[i] = 1
        while st:
            x = po()
            y = la1[x]
            put(x)
            while y is not None:
                z = dat[y]
                if not cnt[z]:
                    cnt[z] = 1
                    pu(z)
                y = xt1[y]
        y = len(t)
        for x in t:
            cnt[x] = y
        ans += y * (y - 1)
        del t[:]
    d = [0] * (n + 1)
    for i in xrange(1, n + 1):
        if d[i]:
            continue
        pu(i)
        d[i] = 1
        while st:
            x = po()
            y = la0[x]
            put(x)
            while y is not None:
                z = dat[y]
                if not d[z]:
                    d[z] = 1
                    pu(z)
                y = xt0[y]
        c = len(t)
        for x in t:
            ans += (c - 1) * (cnt[x] - 1)
        ans += c * (c - 1)
        del t[:]
    print ans
main()
