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
input = sys.stdin.readline
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
if n == 2:
  print(2)
  exit()
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
dp = [[0]*3 for i in range(n+1)]
stack = []
root = 0
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif not root:
    root = i
    deg[root] += 1
while stack:
  x = stack.pop()
  if dp[x][0] == dp[x][1] == 0:
    for y,d in graph[x]:
      dp[y][d] += 1
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
  else:
    for y,d in graph[x]:
      if deg[y] > 1:
        dp[y][d] += dp[x][d]+1
        if d == 1:
          dp[y][2] += dp[x][0]+dp[x][2]
        deg[y] -= 1
        if deg[y] == 1:
          stack.append(y)
stack = [root]
deg[root] -= 1
while stack:
  x = stack.pop()
  for y,d in graph[x]:
    if deg[y] == 1:
      deg[y] -= 1
      dp[y][d] += dp[x][d]-dp[y][d]
      if d == 1:
        dp[y][2] += dp[x][2]+dp[x][0]-dp[y][0]-dp[y][2]
      stack.append(y)
ans = 0
for i,j,k in dp:
  ans += i+j+k
print(ans)