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 + 5;
int n;
long long ans, dp[maxn][2], pd[maxn][2];
int ept, head[maxn], to[maxn * 2], nxt[maxn * 2], cost[maxn * 2];
int read() {
  int res = 0;
  char ch = getchar();
  while (ch == ' ' || ch == '\n') ch = getchar();
  do {
    res = res * 10 + ch - '0';
    ch = getchar();
  } while ('0' <= ch && ch <= '9');
  return res;
}
void add(int u, int v, int w) {
  to[ept] = v, cost[ept] = w, nxt[ept] = head[u];
  head[u] = ept++;
}
void dfs1(int u, int f) {
  dp[u][0] = dp[u][1] = 1;
  for (int i = head[u]; ~i; i = nxt[i]) {
    int t = to[i];
    if (t == f) continue;
    dfs1(t, u);
    dp[u][1] += cost[i] * dp[t][1];
    dp[u][0] += dp[t][cost[i]];
  }
}
void dfs2(int u, int f) {
  ans += dp[u][0] - 1;
  for (int i = head[u]; ~i; i = nxt[i]) {
    int t = to[i];
    if (t == f) continue;
    long long temp[4] = {dp[t][cost[i]], dp[t][1], dp[u][cost[i]],
                         cost[i] * dp[u][1]};
    dp[u][0] -= dp[t][cost[i]];
    dp[u][1] -= dp[t][1];
    dp[t][0] += dp[u][cost[i]];
    dp[t][1] += cost[i] * dp[u][1];
    dfs2(t, u);
    dp[u][0] += temp[0];
    dp[u][1] += temp[1];
    dp[t][0] -= temp[2];
    dp[t][1] -= temp[3];
  }
}
int main() {
  n = read();
  ept = 0;
  memset(head, -1, sizeof head);
  for (int i = 1, u, v, w; i < n; ++i) {
    u = read(), v = read(), w = read();
    add(u, v, w), add(v, u, w);
  }
  memset(dp, 0, sizeof dp);
  dfs1(1, 1);
  ans = 0;
  dfs2(1, 1);
  printf("%I64d\n", ans);
  return 0;
}
