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
from types import GeneratorType

input = lambda :sys.stdin.readline().rstrip()



def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc


n = int(input())
good_num = [0 for i in range(n + 1)]
mid_num = [0 for i in range(n + 1)]
tree = [[] for i in range(n + 1)]
ans = [0]

for i in range(n - 1):
    a, b, c = map(int, input().split())
    tree[a].append((b, c))
    tree[b].append((a, c))

root = 1
@bootstrap
def dfs1(node, pa):
    for ch, cl in tree[node]:
        if ch != pa:
            yield dfs1(ch, node)
            if cl:
                mid_num[node] += good_num[ch] + mid_num[ch] + 1
            else:
                good_num[node] += good_num[ch] + 1
                
    yield 0
dfs1(root, root)


@bootstrap
def dfs2(node, pa, pgood, pmid):
    for ch, cl in tree[node]:
        temp= ans[0]
        if ch!= pa:
            ans[0] += good_num[ch] + mid_num[ch]
            if cl:
                node_good = pgood + good_num[node]
                node_mid = pmid + mid_num[node] - (mid_num[ch] + good_num[ch])
                ans[0] += node_good + node_mid
                #print('good_num child : {}, mid num child: {}'.format(good_num[ch], mid_num[ch]))
                #print('ch: {}, node: {}, pgood: {} , pmid: {}'.format(ch, node, pgood, pmid))
                #print('prev ans: {}, cur ans: {}'.format(temp, ans[0]))
                #input()
                #print(pass_down_mid)
                yield dfs2(ch, node, 0, node_mid + node_good)
            else:
                node_good = pgood + (good_num[node] - good_num[ch])
                ans[0] += node_good
                #print('ch: {}, node: {}, pgood: {} , pmid: {}'.format(ch, node, pgood, pmid))
                #print('prev ans: {}, cur ans: {}'.format(temp, ans[0]))
                #input()
                
                
                yield dfs2(ch, node, node_good, 0)

    yield 0
ans[0] = good_num[root] + mid_num[root]
dfs2(root, root, 0,0)
print(ans[0])
