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
sys.setrecursionlimit(2*10**5)
I = lambda : list(map(int,input().split()))

n,=I()
r=[[1 for i in range(n)],[1 for i in range(n)]]
p=[[i for i in range(n)],[i for i in range(n)]]
def find(x,c):
	if x!=p[c][x]:
		p[c][x]=find(p[c][x],c)
	return p[c][x]

def union(a,b,c):
	x=find(a,c)
	y=find(b,c)
	mm=min(x,y)
	if x!=y:
		p[c][y]=p[c][x]=mm
		r[c][mm]+=r[c][max(x,y)]
an=0
for i in range(n-1):
	a,b,c=I()
	union(a-1,b-1,c)
vis=[0]*n
cc=[]
for i in range(n):
	s0=r[0][i]
	s1=r[1][i]
	if p[0][i]==i:
		an+=(s0-1)*s0
	if p[1][i]==i:
		an+=(s1-1)*s1
	an+=(r[1][find(i,1)]-1)*(r[0][find(i,0)]-1)
print(an)