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;
const long long INF = 5e18;
vector<long long> g1[600001];
long long p[600001][2];
long long sz[600001][2];
long long getpar(long long s, long long t) {
  if (s == p[s][t]) return s;
  return p[s][t] = getpar(p[s][t], t);
}
void merge(long long a, long long b, long long t) {
  long long p1 = getpar(a, t);
  long long p2 = getpar(b, t);
  if (p1 == p2) return;
  if (sz[p1][t] > sz[p2][t]) {
  }
  sz[p2][t] += sz[p1][t] + 1;
  sz[p1][t] = 0;
  p[p1][t] = p[p2][t];
}
void init() {
  for (long long i = 0; i < 600001; i++) {
    p[i][0] = p[i][1] = i;
    sz[i][0] = sz[i][1] = 0;
  }
}
long long cnt[600001][2];
long long used[600001][2];
void solve() {
  long long n;
  cin >> n;
  init();
  for (long long i = 0; i < n - 1; i++) {
    long long a, b, t;
    cin >> a >> b >> t;
    merge(a, b, t);
  }
  long long ans = 0;
  for (long long i = 0; i < n + 1; i++) {
    for (long long j = 0; j < 2; j++) {
      ans += sz[i][j] * (sz[i][j] + 1);
    }
  }
  for (long long i = 0; i < n + 1; i++) {
    long long p1 = getpar(i, 1);
    long long p0 = getpar(i, 0);
    ans += sz[p1][1] * sz[p0][0];
  }
  cout << ans << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  while (t--) {
    solve();
  }
}
