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>
const int oo = 2139063143;
const int N = 1010000;
const int P = 1000000007;
using namespace std;
template <typename T>
inline void sc(T &x) {
  x = 0;
  static int p;
  p = 1;
  static char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c - 48);
    c = getchar();
  }
  x *= p;
}
template <typename T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void pr(T x) {
  print(x), putchar('\n');
}
struct EDGE {
  int v, w, nx;
} lb[N << 1];
int tot = 1, top[N];
void add(int u, int v, int w) {
  lb[++tot] = (EDGE){v, w, top[u]}, top[u] = tot;
}
int siz[N], masiz[N];
bool vis[N];
int st[N], z = 0;
void dfsiz(int u) {
  vis[u] = 1;
  st[++z] = u;
  siz[u] = 1, masiz[u] = 0;
  for (int kb = top[u]; kb; kb = lb[kb].nx) {
    int v = lb[kb].v;
    if (vis[v]) continue;
    dfsiz(v);
    siz[u] += siz[v];
    masiz[u] = max(masiz[u], siz[v]);
  }
  vis[u] = 0;
}
long long ans = 0;
int f[4], g[4];
void calc() {
  ans += (long long)f[0] * (g[0] + g[1] + g[3]);
  ans += (long long)f[1] * g[1];
  ans += (long long)f[2] * g[1];
  ans += (long long)g[0] * (f[0] + f[1] + f[3]);
  ans += (long long)g[1] * f[1];
  ans += (long long)g[2] * f[1];
  for (int i = 0; i <= 3; i++) f[i] += g[i], g[i] = 0;
}
int get(int x, int y) {
  if (x == y) return x;
  if (x == 2 && y == 0) return x;
  if (x == 3 && y == 1) return x;
  if (x == 0 && y == 1) return 3;
  if (x == 1 && y == 0) return 2;
  return -1;
}
void dfs(int u, int x) {
  vis[u] = 1;
  for (int kb = top[u]; kb; kb = lb[kb].nx) {
    int v = lb[kb].v, w = lb[kb].w, y = get(x, w);
    if (y == -1 || vis[v]) continue;
    ++g[y];
    dfs(v, y);
  }
  vis[u] = 0;
}
void solve(int u) {
  z = 0;
  dfsiz(u);
  int sum = siz[u], mi = 1e9;
  for (int i = 1; i <= z; i++) {
    int v = st[i], ma = max(masiz[v], sum - siz[v]);
    if (ma < mi) mi = ma, u = v;
  }
  for (int i = 0; i <= 3; i++) f[i] = g[i] = 0;
  vis[u] = 1;
  for (int kb = top[u]; kb; kb = lb[kb].nx) {
    int v = lb[kb].v, w = lb[kb].w;
    if (vis[v]) continue;
    ++g[w];
    dfs(v, w);
    calc();
  }
  ans += (long long)f[0] * 2 + f[1] * 2 + f[2] + f[3];
  for (int kb = top[u]; kb; kb = lb[kb].nx) {
    int v = lb[kb].v;
    if (vis[v]) continue;
    solve(v);
  }
}
int main() {
  int n;
  sc(n);
  for (int i = 1; i < n; i++) {
    int x, y, w;
    sc(x), sc(y), sc(w);
    add(x, y, w), add(y, x, w);
  }
  solve(1);
  pr(ans);
  return 0;
}
