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>
#pragma GCC optimize("O3")
using namespace std;
long long n, m, k;
const long long maxn = 2e5 + 10;
struct edge {
  long long v;
  long long to;
  long long w;
};
vector<edge> V[maxn];
long long ANS[maxn];
long long D[maxn][5];
void dfs(long long v, long long p) {
  long long q;
  D[v][4]++;
  vector<vector<long long> > X(4);
  vector<long long> S(4);
  for (q = 0; q < V[v].size(); q++) {
    long long v1 = V[v][q].to;
    if (v1 == p) {
      continue;
    }
    dfs(v1, v);
    if (V[v][q].w == 0) {
      D[v][0] += D[v1][0] + D[v1][4];
      D[v][3] += D[v1][1] + D[v1][3];
      X[0].push_back(D[v1][0] + D[v1][4]);
      X[1].push_back(0);
      X[2].push_back(0);
      X[3].push_back(D[v1][1] + D[v1][3]);
    } else {
      D[v][1] += D[v1][1] + D[v1][4];
      D[v][2] += D[v1][2] + D[v1][0];
      X[0].push_back(0);
      X[1].push_back(D[v1][1] + D[v1][4]);
      X[2].push_back(D[v1][2] + D[v1][0]);
      X[3].push_back(0);
    }
  }
  long long i = 0;
  for (q = 0; q < V[v].size(); q++) {
    long long v1 = V[v][q].to;
    if (v1 == p) {
      continue;
    }
    ANS[v] += X[0][i] * (D[v][0] - X[0][i] + D[v][1] - X[1][i] + D[v][3] -
                         X[3][i] + D[v][4]) +
              (X[1][i] + X[2][i]) * (D[v][1] - X[1][i] + D[v][4]);
    i++;
  }
  ANS[v] += D[v][1] + D[v][0] + D[v][3];
}
int main() {
  long long q, w, e, a, b, c;
  cin >> n;
  for (q = 0; q < n - 1; q++) {
    cin >> a >> b >> c;
    edge e, f;
    a--;
    b--;
    e.v = f.to = a;
    e.to = f.v = b;
    e.w = f.w = c;
    V[e.v].push_back(e);
    V[f.v].push_back(f);
  }
  dfs(0, 0);
  long long ans = 0;
  for (q = 0; q < n; q++) {
    ans += ANS[q];
  }
  cout << ans;
  return 0;
}
