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,math
from fractions import gcd
from bisect import bisect_left, bisect
from collections import defaultdict
from io import BytesIO
sys.stdin = BytesIO(sys.stdin.read())
input = lambda: sys.stdin.readline().rstrip('\r\n')
n = int(input())
#n,m,k = [int(_) for _ in input().split()]

gr0 = defaultdict(set)
gr1 = defaultdict(set)
ver0 = set()
krb = dict()
r = []
for i in range(n-1):
    s = input()
    s,f,k = [int(_) for _ in s.split()]
    if k == 0:
        gr0[s].add(f)
        gr0[f].add(s)
        ver0.add(s)
        ver0.add(f)
    else:
        gr1[s].add(f)
        gr1[f].add(s)
    krb[(s,f)] = k
    krb[(f,s)] = k

arr0 = [0] * (n+1)
arr1 = [0] * (n+1)

def color(arr,gr,cur,i):
    top = set()
    top.add(i)
    while len(top):
        x = top.pop()
        arr[x] = cur
        for el in gr[x]:
            if arr[el] == 0:
                top.add(el)


cur = 0
i = 1
while i <= n:
    if arr0[i] or i not in gr0:
        i += 1
        continue
    else:
        cur += 1
        color(arr0,gr0,cur,i)
    i += 1

#print(arr0)

cur1 = 0
i = 1
while i <= n:
    if arr1[i] or i not in gr1:
        i += 1
        continue
    else:
        cur1 += 1
        color(arr1,gr1,cur1,i)
    i += 1
#print(arr1)

res = 0
d0 = defaultdict(int)
d1 = defaultdict(int)

for i in range(n+1):
    if arr0[i]:
        d0[arr0[i]] += 1
    if arr1[i]:
        d1[arr1[i]] += 1
for k in d0:
    if d0[k] > 1:
        x = d0[k]-1
        res += x * (x+1)

for k in d1:
    if d1[k] > 1:
        x = d1[k]-1
        res += x * (x+1)

s = set()
d = defaultdict(int)
for v in ver0:
    d[arr1[v]] += d0[arr0[v]]-1
#print(d)
for k in d:
    if k:
        res += d[k] * (d1[k]-1)
print(res)
