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 int MAXN = 2e5 + 10;
int N;
long long ans;
vector<int> ADJ[MAXN];
vector<int> C[MAXN];
long long D[MAXN][2];
long long DD[MAXN][2];
void dfs(int here, int par) {
  for (int i = 0; i < ADJ[here].size(); i++) {
    int there = ADJ[here][i];
    if (there == par) continue;
    dfs(there, here);
    if (C[here][i]) {
      ans += 2 * D[here][1] * D[there][1];
      D[here][1] += D[there][1];
    } else {
      ans += 2 * D[here][0] * D[there][0];
      D[here][0] += D[there][0];
    }
  }
  ans += D[here][1] * D[here][0];
  ans += 2 * D[here][1];
  ans += 2 * D[here][0];
  D[here][0]++;
  D[here][1]++;
}
void dfs2(int here, int par, int val) {
  for (int i = 0; i < ADJ[here].size(); i++) {
    int there = ADJ[here][i];
    if (there == par) continue;
    if (val != 1)
      DD[there][0] = DD[here][0];
    else
      DD[there][0] = D[here][0];
    if (val != 0)
      DD[there][1] = DD[here][1];
    else
      DD[there][1] = D[here][1];
    dfs2(there, here, C[here][i]);
  }
  if (here == 1) return;
  if (val == 0)
    ans += (D[here][1] - 1) * (DD[here][0] - D[here][0]);
  else
    ans += (D[here][0] - 1) * (DD[here][1] - D[here][1]);
}
int main(void) {
  scanf("%d", &N);
  for (int i = 1; i < N; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    ADJ[x].push_back(y);
    ADJ[y].push_back(x);
    C[x].push_back(z);
    C[y].push_back(z);
  }
  dfs(1, 0);
  DD[1][0] = D[1][0];
  DD[1][1] = D[1][1];
  dfs2(1, 0, -1);
  printf("%lld\n", ans);
  return 0;
}
