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 collections as cc
import itertools as it
import bisect as bi
import sys
sys=sys.stdin.readline
I=lambda:list(map(int,input().split()))
def find(x,i):
	while x!=parent[i][x]:
		x=parent[i][x]
	return x
def union(x,y,i):
	a=find(x,i)
	b=find(y,i)
	parent[i][a]=parent[i][b]=min(a,b)
	if min(a,b)==a:
		sz[i][a]+=sz[i][b]
	else:
		sz[i][b]+=sz[i][a]
n,=I()
parent=[[i for i in range(n+1)] for j in range(2)]
sz=[[1 for i in range(n+1)] for j in range(2)]
for i in range(n-1):
	t=I()
	union(*t)
ans=0
for i in range(1,n+1):
	if parent[0][i]==i:
		ans+=sz[0][i]*(sz[0][i]-1)
	if parent[1][i]==i:
		ans+=sz[1][i]*(sz[1][i]-1)
	ans+=(sz[0][find(i,0)]-1)*(sz[1][find(i,1)]-1)
print(ans)
