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;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
vector<int> p[2];
vector<ll> w[2];
vector<pi> heavy;
int find(int c, int x) { return x == p[c][x] ? x : p[c][x] = find(c, p[c][x]); }
void join(int c, int x, int y) {
  x = find(c, x);
  y = find(c, y);
  if (x == y) return;
  if (w[c][x] < w[c][y]) swap(x, y);
  p[c][y] = x;
  w[c][x] += w[c][y];
}
ll choose2(ll n) { return n * (n - 1) / 2; }
int main() {
  ios_base::sync_with_stdio(false);
  cout << setprecision(12);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int c = 0; c < int(2); c++) {
    p[c].resize(n);
    iota(p[c].begin(), p[c].end(), 0);
    w[c].assign(n, 1);
  }
  for (int i = 0; i < int(n - 1); i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--;
    join(c, x, y);
    heavy.emplace_back(x, y);
  }
  ll ans = 0;
  for (int c = 0; c < int(2); c++)
    for (int x = 0; x < int(n); x++)
      if (x == find(c, x)) ans += 2 * choose2(w[c][x]);
  set<pi> seen;
  for (int i = 0; i < int(n); i++) {
    int x = find(0, i);
    int y = find(1, i);
    if (seen.count({x, y})) continue;
    seen.emplace(x, y);
    ans += (w[0][x] - 1) * (w[1][y] - 1);
  }
  cout << ans << endl;
}
