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;
struct edge {
  int y;
  int nex;
  int v;
} e[maxn << 1];
int head[maxn], cnt;
long long dp[maxn][4];
void adde(int w, int ww, int www) {
  e[cnt].y = ww;
  e[cnt].v = www;
  e[cnt].nex = head[w];
  head[w] = cnt++;
}
long long ans = 0;
void dfs(int u, int f) {
  long long sum1 = 0;
  long long sum2 = 0;
  long long sum3 = 0;
  long long sum4 = 0;
  for (int i = head[u]; i != -1; i = e[i].nex) {
    int z = e[i].y;
    if (z == f) continue;
    dfs(z, u);
    if (e[i].v) {
      dp[u][1] += 1 + dp[z][1];
      dp[u][2] += dp[z][0] + dp[z][2];
      ans += sum1 * (dp[z][1] + 1) * 2 + sum1 * dp[z][2] + dp[z][0] * sum1;
      ans += sum2 * (dp[z][1] + 1);
      ans += sum3 * (dp[z][1] + 1);
      ans += 2 * (1 + dp[z][1]) + dp[z][0] + dp[z][2];
      sum1 += 1 + dp[z][1];
      sum3 += dp[z][0] + dp[z][2];
    } else {
      dp[u][0] += 1 + dp[z][0];
      dp[u][3] += dp[z][1] + dp[z][3];
      ans += sum2 * (dp[z][0] + 1) * 2 + sum2 * dp[z][3] + sum2 * dp[z][1];
      ans += sum1 * (dp[z][0] + 1);
      ans += sum4 * (dp[z][0] + 1);
      ans += 2 * (1 + dp[z][0]) + dp[z][1] + dp[z][3];
      sum2 += 1 + dp[z][0];
      sum4 += dp[z][1] + dp[z][3];
    }
  }
}
int main() {
  int n;
  scanf("%d", &n);
  memset(head, -1, sizeof(head));
  for (int i = 1; i < n; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    adde(a, b, c);
    adde(b, a, c);
  }
  dfs(1, -1);
  printf("%lld\n", ans);
  return 0;
}
