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;
const int N = 2e5 + 5;
int n, lvl[N], par[N][20], col[N][20], sz[N], used[N];
ll ans;
vector<int> adj[N], w[N], cadj[N];
int Merge(int A, int B) {
  if (A == 0 && A == B) return 0;
  if (A == 1 && A == B) return 1;
  if (A == 0 && B == 1) return 2;
  if (A == 0 && B == 2) return 2;
  if (A == 2 && B == 1) return 2;
  if (A == 1 && B == 0) return 3;
  if (A == 1 && B == 3) return 3;
  if (A == 3 && B == 0) return 3;
  return 4;
}
void Make_Lca(int v, int pr = 0, int c = 4) {
  lvl[v] = lvl[pr] + 1;
  par[v][0] = pr;
  col[v][0] = c;
  for (int i = 1; i <= 18; ++i) {
    par[v][i] = par[par[v][i - 1]][i - 1];
    col[v][i] = Merge(col[v][i - 1], col[par[v][i - 1]][i - 1]);
  }
  for (int i = 0; i < adj[v].size(); ++i) {
    if (adj[v][i] != pr) Make_Lca(adj[v][i], v, w[v][i]);
  }
}
int Get(int x, int y) {
  if (lvl[x] >= lvl[y]) {
    int rx = col[x][0];
    for (int i = 18; i >= 0; i--) {
      if (lvl[par[x][i]] >= lvl[y]) {
        rx = Merge(rx, col[x][i]);
        x = par[x][i];
      }
    }
    if (x == y) return rx;
    int ry = col[y][0];
    for (int i = 18; i >= 0; i--) {
      if (par[x][i] != par[y][i]) {
        rx = Merge(rx, col[x][i]);
        ry = Merge(ry, col[y][i]);
        x = par[x][i];
        y = par[y][i];
      }
    }
    rx = Merge(rx, col[x][0]);
    ry = Merge(ry, col[y][0]);
    if (ry == 2)
      ry = 3;
    else if (ry == 3)
      ry = 2;
    rx = Merge(rx, col[x][0]);
    return Merge(rx, ry);
  } else {
    int ry = col[y][0];
    for (int i = 18; i >= 0; i--) {
      if (lvl[par[y][i]] >= lvl[x]) {
        ry = Merge(ry, col[y][i]);
        y = par[y][i];
      }
    }
    if (x == y) {
      if (ry == 2)
        ry = 3;
      else if (ry == 3)
        ry = 2;
      return ry;
    }
    int rx = col[x][0];
    for (int i = 18; i >= 0; i--) {
      if (par[x][i] != par[y][i]) {
        rx = Merge(rx, col[x][i]);
        ry = Merge(ry, col[y][i]);
        x = par[x][i];
        y = par[y][i];
      }
    }
    rx = Merge(rx, col[x][0]);
    ry = Merge(ry, col[y][0]);
    if (ry == 2)
      ry = 3;
    else if (ry == 3)
      ry = 2;
    return Merge(rx, ry);
  }
}
void calc(int v, int pr = 0) {
  sz[v] = 1;
  for (auto to : adj[v]) {
    if (!used[to] && to != pr) calc(to, v), sz[v] += sz[to];
  }
}
int center(int v, int root, int pr = 0) {
  for (auto to : adj[v]) {
    if (!used[to] && to != pr && sz[to] > sz[root] / 2)
      return center(to, root, v);
  }
  return v;
}
void decompos(int v, int pr = 0) {
  calc(v);
  v = center(v, v);
  used[v] = 1;
  cadj[pr].push_back(v);
  for (auto to : adj[v]) {
    if (!used[to]) decompos(to, v);
  }
}
void subtree(int v, int root, vector<int> &cnt) {
  ++cnt[Get(v, root)];
  for (auto to : cadj[v]) subtree(to, root, cnt);
}
void dfs(int v) {
  for (auto to : cadj[v]) dfs(to);
  vector<int> cnt = {0, 0, 0, 0, 0};
  for (auto to : cadj[v]) {
    vector<int> ncnt = {0, 0, 0, 0, 0};
    subtree(to, v, ncnt);
    {
      ans += ncnt[0] * 2;
      ans += ncnt[0] * 1LL * cnt[0] * 2;
      ans += ncnt[0] * 1LL * cnt[1];
      ans += ncnt[0] * 1LL * cnt[3];
    }
    {
      ans += ncnt[1] * 2;
      ans += ncnt[1] * 1LL * cnt[1] * 2;
      ans += ncnt[1] * 1LL * cnt[0];
      ans += ncnt[1] * 1LL * cnt[2];
    }
    {
      ans += ncnt[2];
      ans += ncnt[2] * 1LL * cnt[1];
    }
    {
      ans += ncnt[3];
      ans += ncnt[3] * 1LL * cnt[0];
    }
    for (int i = 0; i < 5; ++i) cnt[i] += ncnt[i];
  }
}
int main() {
  ios ::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    adj[x].push_back(y);
    w[x].push_back(c);
    adj[y].push_back(x);
    w[y].push_back(c);
  }
  Make_Lca(1);
  decompos(1);
  dfs(cadj[0][0]);
  cout << ans;
  return 0;
}
