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>
class dsu:
	def __init__(self,n):
		self.arr = [i for i in range(n)]
		self.size = [1 for i in range(n)]
		self.s = n
	def find(self,i):
		while(i!=self.arr[i]):
			i = self.arr[i]
		return i
		if(self.arr[i]!=i):
			self.arr[i] = self.find(self.arr[i])
		return self.arr[i]
	def union(self,i,j):
		fa = self.find(i)
		fb = self.find(j)
		if(fa == fb):
			return
		s1 = self.size[fa]
		s2 = self.size[fb]
		if(s1<s2):
			self.arr[fa] = fb
			self.size[fb] += self.size[fa]
		else:
			self.arr[fb] = fa
			self.size[fa] += self.size[fb]
n = int(input())
zero = dsu(n)
one = dsu(n)
for i in range(n-1):
	a = [int(i) for i in input().split(' ')]
	x = a[0]-1
	y = a[1]-1
	c = a[2]
	if(c==0):
		zero.union(x,y)
	else:
		one.union(x,y)
count = 0
for i in range(n):
	if(zero.arr[i] == i):
		count+=zero.size[i]*(zero.size[i]-1)
	if(one.arr[i] == i):
		count+=one.size[i]*(one.size[i]-1)
	count += (zero.size[zero.find(i)]-1)*(one.size[one.find(i)]-1)
print(count)