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;
class UF {
  vector<int> root;
  vector<int> sz;

 public:
  UF(int n) {
    root.resize(n + 1);
    sz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      root[i] = i;
      sz[i] = 1;
    }
  }
  int get_root(int node) {
    if (root[node] == node) return root[node];
    root[node] = get_root(root[node]);
    return root[node];
  }
  int get_size(int node) {
    node = get_root(node);
    return sz[node];
  }
  bool connect(int u, int v) {
    u = get_root(u);
    v = get_root(v);
    if (u != v) {
      root[u] = v;
      sz[v] += sz[u];
    }
    return u != v;
  }
};
int main() {
  int n;
  scanf("%d", &n);
  UF zeros(n);
  UF ones(n);
  vector<bool> has_zero(n + 1);
  vector<bool> has_one(n + 1);
  for (int i = 1; i < n; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    if (c == 0) {
      zeros.connect(u, v);
      has_zero[u] = 1;
      has_zero[v] = 1;
    } else {
      ones.connect(u, v);
      has_one[u] = 1;
      has_one[v] = 1;
    }
  }
  unordered_set<int> visited_zero, visited_one;
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    int root_zero = zeros.get_root(i);
    int root_one = ones.get_root(i);
    if (visited_zero.count(root_zero) == 0) {
      visited_zero.insert(root_zero);
      long long sz = zeros.get_size(root_zero);
      ans += sz * (sz - 1);
    }
    if (visited_one.count(root_one) == 0) {
      visited_one.insert(root_one);
      long long sz = ones.get_size(root_one);
      ans += sz * (sz - 1);
    }
    if (has_zero[i] && has_one[i]) {
      long long sz1 = ones.get_size(i);
      long long sz0 = zeros.get_size(i);
      ans += (sz1 - 1) * (sz0 - 1);
    }
  }
  cout << ans << endl;
}
