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 double eps = 1e-6;
const int maxn = 400000 + 5;
int head[maxn], ver[maxn], edge[maxn], nex[maxn];
int pn;
int n;
long long cnt[maxn][3][3];
long long ans = 0;
void addedge(int a, int b, int w);
void dfs(int a, int fa);
int main() {
  scanf("%d", &n);
  pn = 1;
  memset(head, 0, sizeof(head));
  for (int i = 1; i <= n - 1; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    addedge(a, b, w);
    addedge(b, a, w);
  }
  memset(cnt, 0, sizeof(cnt));
  dfs(1, -1);
  printf("%lld\n", ans);
  return 0;
}
void addedge(int a, int b, int w) {
  ver[++pn] = b;
  edge[pn] = w;
  nex[pn] = head[a];
  head[a] = pn;
}
void dfs(int a, int fa) {
  for (int p = head[a]; p; p = nex[p])
    if (ver[p] != fa) {
      const int &b = ver[p];
      dfs(b, a);
      if (edge[p]) {
        cnt[a][1][1] += cnt[b][1][1] + 1;
        cnt[a][0][1] += cnt[b][0][1] + cnt[b][0][0];
      } else {
        cnt[a][1][0] += cnt[b][1][0] + cnt[b][1][1];
        cnt[a][0][0] += cnt[b][0][0] + 1;
      }
    }
  ans += cnt[a][1][0];
  ans += (cnt[a][1][1] + cnt[a][0][0]) * 2;
  ans += cnt[a][0][1];
  for (int p = head[a]; p; p = nex[p])
    if (ver[p] != fa) {
      const int &b = ver[p];
      if (edge[p]) {
        cnt[a][1][1] -= cnt[b][1][1] + 1;
        cnt[a][0][1] -= cnt[b][0][1] + cnt[b][0][0];
        ans +=
            (cnt[b][1][1] + 1) * (cnt[a][0][1] + cnt[a][0][0] + cnt[a][1][1]);
      } else {
        cnt[a][1][0] -= cnt[b][1][0] + cnt[b][1][1];
        cnt[a][0][0] -= cnt[b][0][0] + 1;
        ans += (cnt[b][0][0] + cnt[b][1][1] + cnt[b][1][0] + 1) * cnt[a][0][0];
      }
      if (edge[p]) {
        cnt[a][1][1] += cnt[b][1][1] + 1;
        cnt[a][0][1] += cnt[b][0][1] + cnt[b][0][0];
      } else {
        cnt[a][1][0] += cnt[b][1][0] + cnt[b][1][1];
        cnt[a][0][0] += cnt[b][0][0] + 1;
      }
    }
}
