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;
const long long INF = 3e18;
const long long MAXN = 2e5 + 228;
long long n, used[MAXN], par[MAXN][2], sz[MAXN][2], ans;
vector<vector<pair<long long, long long>>> g(MAXN);
map<pair<long long, long long>, bool> was;
long long get_parent(long long v, long long r) {
  if (par[v][r] == v) return v;
  return par[v][r] = get_parent(par[v][r], r);
}
void unite(long long u, long long v, long long r) {
  long long a = get_parent(u, r);
  long long b = get_parent(v, r);
  if (rand() & 1) {
    swap(a, b);
  }
  par[a][r] = b;
  sz[b][r] += sz[a][r];
}
void dfs(long long v, long long R = -1) {
  used[v] = 1;
  if (get_parent(v, 0) == v) {
    ans += sz[v][0] * (sz[v][0] - 1);
  }
  if (get_parent(v, 1) == v) {
    ans += sz[v][1] * (sz[v][1] - 1);
  }
  for (auto to : g[v]) {
    long long u = to.first, r = to.second;
    if (!used[u]) {
      if ((R == 0 && r == 1) || (R == 1 && r == 0)) {
        long long a = get_parent(v, 1);
        long long b = get_parent(v, 0);
        pair<long long, long long> p = {min(a, b), max(a, b)};
        if (!was[p]) {
          was[p] = true;
          ans += (sz[a][1] - 1) * (sz[b][0] - 1);
        }
      }
      dfs(u, r);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    par[i][0] = par[i][1] = i;
    sz[i][0] = sz[i][1] = 1;
  }
  for (int i = 0; i < n - 1; ++i) {
    long long u, v, r;
    cin >> u >> v >> r;
    g[u].push_back({v, r});
    g[v].push_back({u, r});
    unite(u, v, r);
  }
  for (int i = 1; i <= n; ++i) {
    if (g[i].size() == 1) {
      dfs(i);
      break;
    }
  }
  cout << ans << '\n';
  return 0;
}
