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>
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class EducationalRound64D {

	public static LinkedList<Edge>[] adj;
	public static long ans = 0;
	
	public static toReturn dfs(int current, int parent) {
		long one = 0, zero = 0, zeroOne = 0, oneZero = 0;
		ArrayList<toReturn> child = new ArrayList<toReturn>();
		for(Edge x : adj[current]) {
			if(x.to != parent) {
				toReturn given = dfs(x.to, current);
				if(x.color == 0) {
					ans += given.zero * 2 + 2 + given.oneZero + given.one;
					zero += given.zero + 1;
					oneZero += given.oneZero + given.one;
					child.add(new toReturn(given.zero + 1, 0, 0, given.oneZero + given.one));
				}else {
					ans += given.one * 2 + 2 + given.zeroOne + given.zero;
					one += given.one + 1;
					zeroOne += given.zero + given.zeroOne;
					child.add(new toReturn(0, given.one + 1, given.zero + given.zeroOne, 0));
				}
			}
		}
		for(toReturn x : child) {
			long leftone = one - x.one;
			long leftzero = zero - x.zero;
			long leftoneZero = oneZero - x.oneZero;
			ans += x.one * leftone;
			ans += x.zero * leftzero;
			ans += x.zeroOne * leftone;
			ans += x.zero * leftoneZero;
			ans += x.zero * leftone;
		}
		return new toReturn(zero, one, zeroOne, oneZero);
	}
	
	public static void solve() {
		int n = s.nextInt();
		adj = new LinkedList[n];
		for(int i = 0; i < n; i++) {
			adj[i] = new LinkedList<Edge>();
		}
		for(int i = 0; i < n - 1; i++) {
			int u = s.nextInt() - 1;
			int v = s.nextInt() - 1;
			int color = s.nextInt();
			adj[u].add(new Edge(v, color));
			adj[v].add(new Edge(u, color));
		}
		dfs(0, 0);
		out.println(ans);
	}
	
	public static class Edge {
		int to;
		int color;
		public Edge(int to, int color) {
			this.to = to;
			this.color = color;
		}
	}
	
	public static class toReturn {
		long zero;
		long one;
		long zeroOne;
		long oneZero;
		public toReturn(long zero, long one, long zeroOne, long oneZero) {
			this.zero = zero;
			this.one = one;
			this.zeroOne = zeroOne;
			this.oneZero = oneZero;
		}
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}
