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 atexit, io, sys, collections, math, heapq, fractions
buffer = io.BytesIO() 
sys.stdout = buffer
@atexit.register 
def write(): sys.__stdout__.write(buffer.getvalue())   
#####################################


n = int(raw_input())
siz0 = [1 for u in range(n+1)]
siz1 = [1 for u in range(n+1)]
par0 = [u for u in range(n+1)]
par1 = [u for u in range(n+1)]


def f(u, parent):
	if u != parent[u]: parent[u] = f(parent[u], parent)
	return parent[u]

def merge(parent,size, u,v):
	pu, pv = f(u, parent), f(v, parent)
	if pu != pv:
		if not(size[pu]>=size[pv]): pu,pv = pv,pu	
		parent[pv] = pu
		size[pu] += size[pv]


for _ in range(n-1):
	u,v,w = map(int, raw_input().split())
	if w == 0:
		merge(par0, siz0, u,v)
	else:
		merge(par1, siz1, u,v)

ans = 0
for u in range(1, n+1):
	ans += siz0[f(u,par0)] -1
	ans += siz1[f(u,par1)] -1
	ans += (siz1[f(u,par1)] -1) * (siz0[f(u,par0)] -1)
print ans