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 N = 2e5 + 15;
int a[N], b[N], w[N];
vector<int> adj[N];
long long one[N], zero[N], oz[N];
void cal(int &one_ret, int &zero_ret, int &oz_ret, int to, int tz, int toz,
         int val) {
  one_ret = zero_ret = oz_ret = 0;
  if (val == 0) {
    ++zero_ret;
    zero_ret += tz;
    oz_ret += to;
    oz_ret += toz;
  } else {
    ++one_ret;
    one_ret += to;
  }
}
void dfs(int node, int par) {
  for (int i = 0; i < adj[node].size(); ++i) {
    int id = adj[node][i];
    int ch = a[id] ^ b[id] ^ node;
    if (ch == par) {
      continue;
    }
    dfs(ch, node);
    int o, z, toz;
    cal(o, z, toz, one[ch], zero[ch], oz[ch], w[id]);
    one[node] += o;
    zero[node] += z;
    oz[node] += toz;
  }
}
void dfs2(long long &ret, int node, int par, long long to, long long tz,
          long long toz) {
  to += one[node];
  tz += zero[node];
  toz += oz[node];
  ret += to + tz + toz;
  for (int i = 0; i < adj[node].size(); ++i) {
    int id = adj[node][i];
    int ch = a[id] ^ b[id] ^ node;
    if (ch == par) {
      continue;
    }
    long long tto = to, ttz = tz, ttoz = toz;
    int x, y, z;
    cal(x, y, z, one[ch], zero[ch], oz[ch], w[id]);
    tto -= x, ttz -= y, ttoz -= z;
    int u, v, k;
    cal(u, v, k, tto, ttz, ttoz, w[id]);
    dfs2(ret, ch, node, u, v, k);
  }
}
void solve() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; ++i) {
    scanf("%d%d%d", &a[i], &b[i], &w[i]);
    adj[a[i]].push_back(i);
    adj[b[i]].push_back(i);
  }
  dfs(1, 0);
  long long ret = 0;
  dfs2(ret, 1, 0, 0, 0, 0);
  cout << ret << endl;
}
int main() { solve(); }
