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 gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int lcm(long long int a, long long int b) {
  return a * b / gcd(a, b);
}
long long int fexp(long long int a, long long int b) {
  long long int ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % 1000000007;
    b /= 2;
    a = a * a % 1000000007;
  }
  return ans;
}
long long int inverse(long long int a, long long int p) {
  return fexp(a, p - 2);
}
void ingraph(vector<vector<long long int> >& graph, long long int m) {
  long long int x, y;
  for (long long int i = 0; i < m; i++) {
    cin >> x >> y;
    x--, y--;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
}
long long int modify(long long int n) {
  long long int res = n;
  res %= 1000000007;
  res += 1000000007;
  res %= 1000000007;
  return res;
}
struct vertex {
  long long int parent;
  long long int rank;
  long long int comp;
  vector<long long int> vec;
};
struct vertex zero[200005], one[200005];
long long int find(long long int n, struct vertex ver[]) {
  long long int x = n;
  while (x != ver[x].parent) {
    x = ver[x].parent;
  }
  long long int y = n;
  long long int z = ver[y].parent;
  while (y != z) {
    ver[y].parent = x;
    y = z;
    z = ver[z].parent;
  }
  return x;
}
void makeset(long long int n, struct vertex ver[]) {
  ver[n].rank = 0;
  ver[n].parent = n;
  ver[n].comp = 1;
  ver[n].vec.push_back(n);
}
void initiate(long long int n, struct vertex ver[]) {
  for (long long int i = 0; i < n; i++) makeset(i, ver);
}
void join(vector<long long int>& x, vector<long long int>& y) {
  x.insert(x.end(), y.begin(), y.end());
}
void uni(long long int x, long long int y, struct vertex ver[]) {
  long long int px = find(x, ver);
  long long int py = find(y, ver);
  if (px == py)
    return;
  else if (ver[px].rank > ver[py].rank) {
    ver[py].parent = px;
    ver[px].comp += ver[py].comp;
    join(ver[px].vec, ver[py].vec);
  } else if (ver[py].rank > ver[px].rank) {
    ver[px].parent = py;
    ver[py].comp += ver[px].comp;
    join(ver[py].vec, ver[px].vec);
  } else {
    ver[py].parent = px;
    ver[px].rank++;
    ver[px].comp += ver[py].comp;
    join(ver[px].vec, ver[py].vec);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int t;
  t = 1;
  while (t--) {
    long long int n;
    cin >> n;
    initiate(n, zero);
    initiate(n, one);
    long long int x, y, w;
    for (long long int i = 0; i < n - 1; i++) {
      cin >> x >> y >> w;
      --x, --y;
      if (w == 0) {
        uni(x, y, zero);
      } else
        uni(x, y, one);
    }
    long long int ans = 0;
    for (long long int i = 0; i < n; i++) {
      long long int a = find(i, zero);
      long long int b = find(i, one);
      ans += (zero[a].comp - 1) + (one[b].comp - 1) +
             (zero[a].comp - 1) * (one[b].comp - 1);
    }
    cout << ans;
  }
}
