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;
//我们不走先过1再过0的边，所以要么两点之间的路径全0，要么全1，要么先过0再过1，用并查集合并相邻的同样的路径
//并查集的解法有点没看懂，又找到一个树形dp的解法
public class Main {
	static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static class edge{
		int v,next,w;
		public edge(int v, int next, int w) {
			super();
			this.v = v;
			this.next = next;
			this.w = w;
		}
			
	}
	static edge e[]=new edge[400010];
	static int p[]=new int[200010];
	static int fa[]=new int[200010];
	static int find(int x){
		return x==fa[x]?x:(fa[x]=find(fa[x]));
	}
	static void insert(int u,int v,int w){
		e[eid]=new edge(v,p[u],w);
		p[u]=eid++;
	}
	static int n,eid;
	static long ans=0;
	static int f[][]=new int[200010][4];
	static void dfs(int u,int fa){
		for(int i=p[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			if(v==fa)
				continue;
			dfs(v,u);
			if(e[i].w==1){
				ans+=(long)2*f[u][1]*(f[v][1]+1);
				ans+=(long)(f[u][0]+f[u][3])*(f[v][1]+1);
				ans+=(long)f[u][1]*(f[v][0]+f[v][3]);
				
				f[u][1]+=f[v][1]+1;
				f[u][3]+=f[v][3];
				f[u][3]+=f[v][0];
			}else{
				ans+=(long)2*f[u][0]*(f[v][0]+1);
	            ans+=(long)(f[u][1]+f[u][2])*(f[v][0]+1);
	            ans+=(long)f[u][0]*(f[v][1]+f[v][2]);

	            f[u][0]+=f[v][0]+1;
	            f[u][2]+=f[v][2];
	            f[u][2]+=f[v][1];

			}
		}
		ans+=2*f[u][0];
		ans+=2*f[u][1];
		ans+=f[u][2];
		ans+=f[u][3];
	}
	public static void main(String[] args) {
		n=nextInt();
		eid=0;
		for(int i=0;i<=n;i++){
			//fa[i]=i;
			p[i]=-1;
		}
		int x,y,c;
		for(int i=1;i<n;i++){
			x=nextInt();
			y=nextInt();
			c=nextInt();
			insert(x,y,c);
			insert(y,x,c);
		}
		dfs(1,0);
		System.out.println(ans);
	}
	static int nextInt(){
		try {
			st.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)st.nval;
	}
}
