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>
def process(e):
    answer = 0
    graphs = [{}, {}]
    def find_root(x, i):
        g = graphs[i]
        L = []
        while x != g[x]:
            L.append(x)
            x = g[x]
        for y in L:
            g[y] = x
        return x
    for a, b, w in e:
        g = graphs[w]
        if a not in g and b not in g:
            g[a] = min(a, b)
            g[b] = min(a, b)
        elif b not in g:
            a2 = find_root(a, w)
            g[b] = a2
        elif a not in g:
            b2 = find_root(b, w)
            g[a] = b2
        else:
            a2 = find_root(a, w)
            b2 = find_root(b, w)
            g[a2] = min(a2, b2)
            g[b2] = min(a2, b2)
    roots = [{}, {}]
    for i in range(2):
        for x in graphs[i]:
            x2 = find_root(x, i)
            if x2 not in roots[i]:
                roots[i][x2] = 0
            roots[i][x2]+=1
        for x in roots[i]:
            answer+=(roots[i][x])*(roots[i][x]-1)
 #   print(roots)
  #  print(answer)
    for x in graphs[0]:
        if x in graphs[1]:
         #   print(x)
            x1 = find_root(x, 0)
            x2 = find_root(x, 1)
            answer+=((roots[0][x1]-1)*(roots[1][x2]-1))
    return answer


n = int(input())
e = []
for i in range(n-1):
    a, b, w = [int(x) for x in input().split()]
    e.append([a, b, w])
print(process(e))