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;
template <class T>
inline bool chmax(T &a, const T &b) {
  return b > a ? a = b, true : false;
}
template <class T>
inline bool chmin(T &a, const T &b) {
  return b < a ? a = b, true : false;
}
template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T, class F = less<T>>
void sort_uniq(vector<T> &v, F f = F()) {
  sort(begin(v), end(v), f);
  v.resize(unique(begin(v), end(v)) - begin(v));
}
struct UnionFind {
  int n, num;
  vector<int> sz, par;
  UnionFind() {}
  UnionFind(int n_) : n(n_), num(n_), sz(n_, 1), par(n_, 0) {
    iota(par.begin(), par.end(), 0);
  }
  int find(int x) { return (x == par[x] ? x : par[x] = find(par[x])); }
  bool same(int x, int y) { return find(x) == find(y); }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    par[y] = x;
    num--;
  }
  int size(int x) { return sz[find(x)]; }
  int count() const { return num; }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  UnionFind uf0(n), uf1(n);
  for (int i = 0; i < (int)(n - 1); i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    if (c)
      uf1.unite(a, b);
    else
      uf0.unite(a, b);
  }
  int64_t ans = 0;
  for (int i = 0; i < (int)(n); i++) {
    if (uf0.find(i) == i) ans += (int64_t)uf0.size(i) * (uf0.size(i) - 1);
    if (uf1.find(i) == i) ans += (int64_t)uf1.size(i) * (uf1.size(i) - 1);
    ans += (int64_t)(uf0.size(i) - 1) * (uf1.size(i) - 1);
  }
  cout << ans << '\n';
  return 0;
}
