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;
vector<vector<pair<int, int>>> g(200001);
long long int siz = 0;
vector<int> temp;
long long int ans = 0;
long long int tot = 0;
bool vis[200001] = {};
long long int calc[200001];
void dfs(int u, int par) {
  siz++;
  temp.push_back(u);
  for (auto i : g[u]) {
    if (i.first == par || i.second == 0) {
      continue;
    }
    dfs(i.first, u);
  }
}
void dfs2(int u, int par) {
  siz++;
  temp.push_back(u);
  vis[u] = 1;
  tot += calc[u];
  for (auto i : g[u]) {
    if (i.first == par || i.second == 1 || vis[i.first]) {
      continue;
    }
    dfs2(i.first, u);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int test = 1;
  while (test--) {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
      calc[i] = -1;
      int u, v, t;
      cin >> u >> v >> t;
      g[u].push_back({v, t});
      g[v].push_back({u, t});
    }
    calc[n] = -1;
    for (int i = 1; i <= n; i++) {
      if (calc[i] != -1) {
        continue;
      }
      dfs(i, -1);
      for (int i = 0; i < siz; i++) {
        calc[temp[i]] = siz - 1;
      }
      ans += ((siz) * (siz - 1));
      temp.clear();
      siz = 0;
    }
    for (int i = 1; i <= n; i++) {
      if (vis[i]) {
        continue;
      }
      dfs2(i, -1);
      for (int i = 0; i < siz; i++) {
        ans += (tot - calc[temp[i]]);
      }
      ans += ((siz) * (siz - 1));
      temp.clear();
      siz = 0;
      tot = 0;
    }
    cout << ans << endl;
  }
  return 0;
}
