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;
namespace zyt {
template <typename T>
inline bool read(T &x) {
  char c;
  bool f = false;
  x = 0;
  do c = getchar();
  while (c != EOF && c != '-' && !isdigit(c));
  if (c == EOF) return false;
  if (c == '-') f = true, c = getchar();
  do x = x * 10 + c - '0', c = getchar();
  while (isdigit(c));
  if (f) x = -x;
  return true;
}
template <typename T>
inline void write(T x) {
  static char buf[20];
  char *pos = buf;
  if (x < 0) putchar('-'), x = -x;
  do *pos++ = x % 10 + '0';
  while (x /= 10);
  while (pos > buf) putchar(*--pos);
}
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, head[N], ecnt;
long long ans;
struct edge {
  int to, w, next;
} e[N << 1];
inline void add(const int a, const int b, const int c) {
  e[ecnt] = (edge){b, c, head[a]}, head[a] = ecnt++;
}
namespace Point_Divide_Conquer {
int rot, tot, size[N], f[N];
bool vis[N];
void findrot(const int u, const int fa) {
  size[u] = 1, f[u] = 0;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (vis[v] || v == fa) continue;
    findrot(v, u);
    size[u] += size[v];
    f[u] = max(f[u], size[v]);
  }
  f[u] = max(f[u], tot - size[u]);
  if (f[u] < f[rot]) rot = u;
}
void get_size(const int u, const int fa) {
  size[u] = 1;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (v == fa || vis[v]) continue;
    get_size(v, u);
    size[u] += size[v];
  }
}
void get_path(const int u, const int fa, const int w, const int st, int &num0,
              int &num1) {
  if (!w)
    ++num0;
  else
    ++num1;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (vis[v] || v == fa || (w != st && e[i].w == st)) continue;
    get_path(v, u, e[i].w, st, num0, num1);
  }
}
void solve(const int u) {
  vis[u] = true;
  int num00 = 0, num01 = 0, num10 = 0, num11 = 0;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (vis[v]) continue;
    int tmp0 = 0, tmp1 = 0;
    if (!e[i].w) {
      get_path(v, u, 0, 0, tmp0, tmp1);
      ans += tmp0 * 2 + tmp1;
      ans += (long long)num00 * (tmp0 + tmp1);
      ans += (long long)tmp0 * (num00 + num01 + num11);
      num00 += tmp0, num01 += tmp1;
    } else {
      get_path(v, u, 1, 1, tmp0, tmp1);
      ans += tmp1 * 2 + tmp0;
      ans += (long long)(num00 + num10 + num11) * tmp1;
      ans += (long long)(tmp0 + tmp1) * num11;
      num10 += tmp0, num11 += tmp1;
    }
  }
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to;
    if (vis[v]) continue;
    get_size(v, u);
    tot = size[v];
    rot = 0, f[0] = INF;
    findrot(v, u);
    solve(rot);
  }
}
}  // namespace Point_Divide_Conquer
int work() {
  using namespace Point_Divide_Conquer;
  read(n);
  memset(head, -1, sizeof(int[n + 1]));
  for (int i = 1; i < n; i++) {
    int a, b, c;
    read(a), read(b), read(c);
    add(a, b, c), add(b, a, c);
  }
  tot = n;
  rot = 0, f[0] = INF;
  findrot(1, 0);
  solve(rot);
  write(ans);
  return 0;
}
}  // namespace zyt
int main() { return zyt::work(); }
