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<pair<long long, long long>> adj[200001];
bool vis[200001];
long long ans = 0;
vector<long long> dfs(long long x) {
  vis[x] = 1;
  vector<long long> v(4, 0);
  long long a, i;
  for (i = 0; i < adj[x].size(); i++) {
    a = adj[x][i].first;
    if (!vis[a]) {
      long long z = adj[x][i].second;
      vector<long long> y = dfs(a);
      if (z == 0) {
        y[0] = y[0] + y[1] + 1;
        y[2] = y[2] + 1;
        y[1] = 0;
        y[3] = 0;
      } else {
        y[1] = y[1] + 1;
        y[3] = y[2] + y[3] + 1;
        y[2] = 0;
        y[0] = 0;
      }
      ans += v[2] * (y[1] + y[0]);
      ans += v[3] * y[1];
      ans += y[2] * (v[1] + v[0]);
      ans += y[3] * v[1];
      if (z == 0) {
        v[0] += y[0] + y[1];
        v[2] += y[2];
      } else {
        v[1] += y[1];
        v[3] += y[2] + y[3];
      }
    }
  }
  ans += v[0] + v[1] + v[2] + v[3];
  return v;
}
int main() {
  long long n, i, x, y, c;
  cin >> n;
  for (i = 0; i < n - 1; i++) {
    cin >> x >> y >> c;
    adj[x].push_back(make_pair(y, c));
    adj[y].push_back(make_pair(x, c));
  }
  vector<long long> v;
  vector<long long> b(2, 0);
  v = dfs(1);
  cout << ans;
}
