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>
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  char ch;
  while (blank(ch = nc()))
    ;
  if (IOerror) return;
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
}
};  // namespace fastIO
using namespace fastIO;
using namespace std;
const int maxN = 2e5 + 7;
int N, root[2][maxN], siz[2][maxN];
inline int fid(int *fa, int x) {
  return x == fa[x] ? x : fa[x] = fid(fa, fa[x]);
}
inline void Merge(int *fa, int *siz, int x, int y) {
  int u = fid(fa, x), v = fid(fa, y);
  if (u != v) {
    fa[u] = v;
    siz[v] += siz[u];
  }
}
inline void init() {
  for (int i = 1; i <= N; i++) root[0][i] = root[1][i] = i;
  for (int i = 1; i <= N; i++) siz[0][i] = siz[1][i] = 1;
}
int main() {
  read(N);
  init();
  for (int i = 1, u, v, w; i < N; i++) {
    read(u);
    read(v);
    read(w);
    Merge(root[w], siz[w], u, v);
  }
  long long ans = 0;
  for (int i = 1; i <= N; i++) {
    ans += (long long)siz[0][fid(root[0], i)] *
               (long long)siz[1][fid(root[1], i)] -
           1;
  }
  printf("%lld\n", ans);
  return 0;
}
