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 = 200005;
int n, a[maxn], k, grp[maxn][2];
bool mark[maxn], marker[maxn];
vector<int> vec[maxn][2], vtx;
set<int> s, t, con;
long long int ans, cnt[maxn], cnter[maxn], dp[maxn];
void dfs(int v) {
  mark[v] = true;
  s.erase(v);
  grp[v][1] = k;
  cnt[k]++;
  for (int u : vec[v][1]) {
    if (!mark[u]) dfs(u);
  }
}
void add(int v) {
  t.erase(v);
  cnter[k]++;
  grp[v][0] = k;
  marker[v]++;
  vtx.push_back(v);
  for (int u : vec[v][0]) {
    if (!marker[u]) add(u);
  }
}
int main() {
  for (int i = 0; i < maxn; i++) grp[i][1] = -1;
  scanf("%d", &n);
  bool flag;
  for (int u, v, i = 1; i < n; i++) {
    scanf("%d%d", &u, &v);
    cin >> flag;
    vec[v][flag].push_back(u);
    vec[u][flag].push_back(v);
    s.insert(i);
    if (!flag) {
      t.insert(u);
      t.insert(v);
    }
  }
  while (!s.empty()) {
    dfs(*s.begin());
    k++;
  }
  for (int i = 0; i < k; i++) ans += cnt[i] * (cnt[i] - 1);
  k = 0;
  while (!t.empty()) {
    add(*t.begin());
    ans += cnter[k] * (cnter[k] - 1);
    int sz = vtx.size();
    while (!vtx.empty()) {
      if (~grp[vtx.back()][1]) {
        dp[grp[vtx.back()][1]]++;
        con.insert(grp[vtx.back()][1]);
      }
      vtx.pop_back();
    }
    while (!con.empty()) {
      ans += (cnter[k] - dp[*con.begin()]) *
             (cnt[*con.begin()] - dp[*con.begin()]);
      dp[*con.begin()] = false;
      con.erase(*con.begin());
    }
    k++;
  }
  cout << ans;
  return 0;
}
