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;
vector<pair<int, int> > vi[200200];
int pone[200200], pzero[200200], size1[200200], size0[200200];
int root0(int x) {
  if (pzero[x] == x)
    return x;
  else
    return pzero[x] = root0(pzero[x]);
}
int root1(int x) {
  if (pone[x] == x)
    return x;
  else
    return pone[x] = root1(pone[x]);
}
long long int rose;
int visit[200200];
int total[200200][2];
int main() {
  int n, m, i, j, k, x, y, ans, temp, last, curr, rootx, rooty;
  scanf("%d", &n);
  rose = 0;
  for (i = 1; i <= n; i++) {
    pone[i] = i;
    pzero[i] = i;
    size0[i] = 1;
    size1[i] = 1;
  }
  for (i = 1; i < n; i++) {
    scanf("%d %d %d", &x, &y, &curr);
    vi[x].push_back(make_pair(y, curr));
    vi[y].push_back(make_pair(x, curr));
    if (curr == 0) {
      rootx = root0(x);
      rooty = root0(y);
      if (rootx == rooty) continue;
      pzero[rootx] = rooty;
      size0[rooty] += size0[rootx];
    } else {
      rootx = root1(x);
      rooty = root1(y);
      if (rootx == rooty) continue;
      pone[rootx] = rooty;
      size1[rooty] += size1[rootx];
    }
  }
  for (i = 1; i <= n; i++) {
    temp = root0(i);
    total[i][0] = size0[temp];
    if (visit[temp] == 0) {
      visit[temp] = 1;
      rose += (1LL * size0[temp] * (size0[temp] - 1));
    }
  }
  memset(visit, 0, sizeof(visit));
  for (i = 1; i <= n; i++) {
    temp = root1(i);
    total[i][1] = size1[temp];
    if (visit[temp] == 0) {
      visit[temp] = 1;
      rose += (1LL * size1[temp] * (size1[temp] - 1));
    }
  }
  for (i = 1; i <= n; i++) {
    rose += (1LL * (total[i][0] - 1) * (total[i][1] - 1));
  }
  printf("%lld\n", rose);
  return 0;
}
