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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
	static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static final int N=(int) (1e6+10);
	static int sz1[]=new int[N];
	static int sz2[]=new int[N];
	static int fa1[]=new int[N];
	static int fa2[]=new int[N];
	static int find1(int x){
		return fa1[x]==x?x:(fa1[x]=find1(fa1[x]));
	}
	static int find2(int x){
		return fa2[x]==x?x:(fa2[x]=find2(fa2[x]));
	}
	static void merge1(int x,int y){
		int a=find1(x);
		int b=find1(y);
		if(a!=b){
			fa1[a]=b;
			sz1[b]+=sz1[a];
		}
	}
	static void merge2(int x,int y){
		int a=find2(x);
		int b=find2(y);
		if(a!=b){
			fa2[a]=b;
			sz2[b]+=sz2[a];
		}
	}
	public static void main(String[] args) {
		int n=nextInt();
		for(int i=1;i<=n;i++){
			sz1[i]=sz2[i]=1;
			fa1[i]=fa2[i]=i;
		}
		for(int i=1;i<n;i++){
			int u,v,w;
			u=nextInt();
			v=nextInt();
			w=nextInt();
			if(w==1){
				merge1(u,v);
			}else{
				merge2(u,v);
			}
		}
		long ans=0;
		for(int i=1;i<=n;i++){
			ans+=(long)sz1[find1(i)]*sz2[find2(i)]-1;
		}
		System.out.println(ans);
	}
	static int nextInt(){
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)st.nval;
	}
}
