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;
int rdn() {
  int ret = 0;
  bool fx = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') fx = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
  return fx ? ret : -ret;
}
int Mx(int a, int b) { return a > b ? a : b; }
int Mn(int a, int b) { return a < b ? a : b; }
const int N = 2e5 + 5, M = 5;
int n, hd[N], xnt, to[N << 1], nxt[N << 1];
bool w[N << 1];
int siz[N], mn, rt, c[M];
long long ans;
bool vis[N];
void add(int x, int y, bool z) {
  to[++xnt] = y;
  nxt[xnt] = hd[x];
  hd[x] = xnt;
  w[xnt] = z;
}
void get_rt(int cr, int fa, int s) {
  siz[cr] = 1;
  int mx = 0;
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]] && v != fa) {
      get_rt(v, cr, s);
      siz[cr] += siz[v];
      mx = Mx(mx, siz[v]);
    }
  mx = Mx(mx, s - siz[cr]);
  if (mx < mn) mn = mx, rt = cr;
}
void dfs(int cr, int fa, int lx, int k) {
  if (lx == 0 || lx == 3) c[lx] += k;
  if (lx == 2) c[1] += k;
  if (lx == 1) c[2] += k;
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]] && v != fa) {
      if (!w[i]) {
        if (lx == 0 || lx == 2) dfs(v, cr, lx, k);
        if (lx == 3) dfs(v, cr, 2, k);
      } else {
        if (lx == 3) dfs(v, cr, lx, k);
        if (lx == 0 || lx == 1) dfs(v, cr, 1, k);
      }
    }
}
void dfsx(int cr, int fa, int lx) {
  if (lx == 0 || lx == 1) ans += c[0];
  if (lx == 3) ans += (long long)c[0] + c[1] + c[3];
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]] && v != fa) {
      if (w[i]) {
        if (lx == 1 || lx == 3) dfsx(v, cr, lx);
        if (lx == 0) dfsx(v, cr, 1);
      } else if (lx == 0)
        dfsx(v, cr, lx);
    }
}
void solve(int cr, int s) {
  vis[cr] = 1;
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]]) dfs(v, cr, (w[i] ? 3 : 0), 1);
  ans += (long long)c[0] * 2 + c[1] + c[2] + c[3] * 2;
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]]) {
      dfs(v, cr, (w[i] ? 3 : 0), -1);
      dfsx(v, cr, (w[i] ? 3 : 0));
      dfs(v, cr, (w[i] ? 3 : 0), 1);
    }
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]]) dfs(v, cr, (w[i] ? 3 : 0), -1);
  for (int i = hd[cr], v; i; i = nxt[i])
    if (!vis[v = to[i]]) {
      int ts = (siz[v] > siz[cr]) ? s - siz[cr] : siz[v];
      mn = N;
      get_rt(v, cr, ts);
      solve(rt, ts);
    }
}
int main() {
  n = rdn();
  for (int i = 1, u, v, z; i < n; i++) {
    u = rdn();
    v = rdn();
    z = rdn();
    add(u, v, z);
    add(v, u, z);
  }
  mn = N;
  get_rt(1, 0, n);
  solve(rt, n);
  printf("%lld\n", ans);
  return 0;
}
