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;
vector<int> adj[MAXN], val[MAXN];
int del[MAXN];
int size[MAXN];
long long has[2], tot[2][2];
long long ans;
void dfs(int u, int p) {
  size[u] = 1;
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v != p && !del[v]) {
      dfs(v, u);
      size[u] += size[v];
    }
  }
}
int findcentroid(int u) {
  int p = -1;
  dfs(u, -1);
  int cap = size[u] >> 1;
  while (1) {
    bool found = false;
    for (int i = 0; i < adj[u].size(); i++) {
      int v = adj[u][i];
      if (v != p && !del[v] && size[v] > cap) {
        found = true;
        p = u;
        u = v;
        break;
      }
    }
    if (!found) return u;
  }
}
void go(int u, int p, int g, int cnt) {
  for (int i = 0; i < (int)adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == p || del[v]) continue;
    int t = val[u][i];
    if (t != g && cnt) continue;
    has[t]++;
    go(v, u, t, cnt | (t != g));
  }
}
void work(int u) {
  tot[0][0] = tot[0][1] = tot[1][0] = tot[1][1] = 0;
  for (int i = 0; i < (int)adj[u].size(); i++) {
    has[0] = has[1] = 0;
    int v = adj[u][i];
    if (del[v]) continue;
    int t = val[u][i];
    has[t]++;
    go(v, u, t, 0);
    if (t) {
      ans += has[1] * 2;
      ans += has[0];
      ans += has[0] * tot[1][0];
      ans += has[1] * tot[1][0] * 2;
      ans += has[1] * tot[1][1];
      ans += has[1] * tot[0][0];
      tot[1][0] += has[1];
      tot[1][1] += has[0];
    } else {
      ans += has[0] * 2;
      ans += has[1];
      ans += has[1] * tot[0][0];
      ans += has[0] * tot[0][0] * 2;
      ans += has[0] * tot[0][1];
      ans += has[0] * tot[1][0];
      tot[0][0] += has[0];
      tot[0][1] += has[1];
    }
  }
}
void divide(int u) {
  u = findcentroid(u);
  del[u] = 1, work(u);
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (!del[v]) {
      divide(v);
    }
  }
}
int main() {
  cin >> n;
  for (int i = (0); i < (n - 1); i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x--;
    y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
    val[x].push_back(z);
    val[y].push_back(z);
  }
  divide(0);
  cout << ans;
  return 0;
}
