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>
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
long long int power(long long int a, long long int b) {
  if (b == 0)
    return 1;
  else if (b % 2 == 0) {
    return power(a * a % mod, b / 2);
  } else
    return (a * power(a * a % mod, b / 2)) % mod;
}
vector<int> v[300006];
bool visited[300006];
long long int parent[3000006];
long long int root(long long int a[][2], long long int i, long long int c) {
  while (a[i][c] != i) {
    i = a[i][c];
  }
  return i;
}
void un(long long int a[][2], long long int size[][2], long long int x,
        long long int y, long long int c) {
  long long int p = root(a, x, c);
  long long int q = root(a, y, c);
  if (size[p][c] < size[q][c]) {
    a[p][c] = a[q][c];
    size[q][c] += size[p][c];
  } else {
    a[q][c] = a[p][c];
    size[p][c] += size[q][c];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n;
  cin >> n;
  long long int a[n][2];
  long long int size[n][2];
  for (int i = 0; i < n; ++i)
    a[i][0] = i, a[i][1] = i, size[i][0] = 1, size[i][1] = 1;
  for (int i = 0; i < n - 1; ++i) {
    long long int p, q, c;
    cin >> p >> q >> c;
    if (root(a, p - 1, c) != root(a, q - 1, c)) un(a, size, p - 1, q - 1, c);
  }
  long long int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i][0] == i) {
      ans += size[i][0] * (size[i][0] - 1);
    }
    if (a[i][1] == i) {
      ans += size[i][1] * (size[i][1] - 1);
    }
    ans += (size[root(a, i, 0)][0] - 1) * (size[root(a, i, 1)][1] - 1);
  }
  cout << ans << endl;
}
