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;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <class T>
auto add = [](T a, T b) -> T { return a + b; };
template <class T>
auto f_max = [](T a, T b) -> T { return max(a, b); };
template <class T>
auto f_min = [](T a, T b) -> T { return min(a, b); };
template <class T>
using V = vector<T>;
using Vl = V<long long int>;
using VVl = V<Vl>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}
template <class T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long int ceil(long long int a, long long int b) { return (a + b - 1) / b; }
long long int digit(long long int a) { return (long long int)log10(a); }
long long int e_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) +
         abs(a.second - b.second) * abs(a.second - b.second);
}
long long int m_dist(pair<long long int, long long int> a,
                     pair<long long int, long long int> b) {
  return abs(a.first - b.first) + abs(a.second - b.second);
}
void Worshall_Floyd(VVl& g) {
  for (long long int k = (0), k_end_ = (((long long int)(g).size()));
       k < k_end_; ++k)
    for (long long int i = (0), i_end_ = (((long long int)(g).size()));
         i < i_end_; ++i)
      for (long long int j = (0), j_end_ = (((long long int)(g).size()));
           j < j_end_; ++j)
        chmin(g[i][j], g[i][k] + g[k][j]);
}
const long long int MOD1000000007 = 1000000007, MOD998244353 = 998244353,
                    INF = 1e18;
long long int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1},
              dy[8] = {0, 1, 0, -1, -1, -1, 1, 1};
bool YN(bool flag) {
  cout << (flag ? "YES" : "NO") << '\n';
  return flag;
}
bool yn(bool flag) {
  cout << (flag ? "Yes" : "No") << '\n';
  return flag;
}
struct Edge {
  long long int from, to;
  long long int cost;
  Edge(long long int u, long long int v, long long int c) {
    cost = c;
    from = u;
    to = v;
  }
  bool operator<(const Edge& e) const { return cost < e.cost; }
};
struct WeightedEdge {
  long long int to;
  long long int cost;
  WeightedEdge(long long int v, long long int c = 1) {
    to = v;
    cost = c;
  }
  bool operator<(const WeightedEdge& e) const { return cost < e.cost; }
};
using WeightedGraph = V<V<WeightedEdge>>;
struct UnionFind {
 public:
  UnionFind() : _n(0) {}
  UnionFind(int n) : _n(n), parent_or_size(n, -1) {}
  int merge(int a, int b) {
    assert(0 <= a && a < _n);
    assert(0 <= b && b < _n);
    int x = leader(a), y = leader(b);
    if (x == y) return x;
    if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
    if (used_count) {
      if (count_in_set[x].size() < count_in_set[y].size()) {
        std::swap(count_in_set[x], count_in_set[y]);
      }
      for (auto p : count_in_set[y]) {
        count_in_set[x][p.first] += p.second;
      }
    }
    if (set_operate) {
      root_values[x] = f(root_values[y], root_values[x]);
    }
    parent_or_size[x] += parent_or_size[y];
    parent_or_size[y] = x;
    return x;
  }
  bool same(int a, int b) {
    assert(0 <= a && a < _n);
    assert(0 <= b && b < _n);
    return leader(a) == leader(b);
  }
  int leader(int a) {
    assert(0 <= a && a < _n);
    if (parent_or_size[a] < 0) return a;
    return parent_or_size[a] = leader(parent_or_size[a]);
  }
  int size(int a) {
    assert(0 <= a && a < _n);
    return -parent_or_size[leader(a)];
  }
  std::vector<std::vector<int>> groups() {
    std::vector<int> leader_buf(_n), group_size(_n);
    for (int i = 0; i < _n; i++) {
      leader_buf[i] = leader(i);
      group_size[leader_buf[i]]++;
    }
    std::vector<std::vector<int>> result(_n);
    for (int i = 0; i < _n; i++) {
      result[i].reserve(group_size[i]);
    }
    for (int i = 0; i < _n; i++) {
      result[leader_buf[i]].push_back(i);
    }
    result.erase(
        std::remove_if(result.begin(), result.end(),
                       [&](const std::vector<int>& v) { return v.empty(); }),
        result.end());
    return result;
  }
  void set_operate_and_value(
      std::vector<long long int> array,
      function<long long int(long long int, long long int)> _f) {
    f = _f;
    root_values = array;
    set_operate = true;
  }
  long long int get_set_value(int a) { return root_values[leader(a)]; }
  void regist_count(int a, int label) {
    if (!used_count) {
      used_count = true;
      count_in_set.assign(_n, std::map<int, int>());
    }
    count_in_set[leader(a)][label]++;
  }
  int get_count(int a, int label) {
    if (!used_count) return -1;
    return count_in_set[leader(a)][label];
  }

 private:
  int _n;
  std::vector<int> parent_or_size;
  std::vector<std::map<int, int>> count_in_set;
  bool used_count = false;
  std::vector<long long int> root_values;
  function<long long int(long long int, long long int)> f;
  bool set_operate = false;
};
long long int N, u, v, c;
int main() {
  cin >> N;
  UnionFind tree0(N), tree1(N);
  long long int ans = 0;
  for (long long int i = (0), i_end_ = (N - 1); i < i_end_; ++i) {
    cin >> u >> v >> c;
    u--;
    v--;
    if (c == 0) {
      tree0.merge(u, v);
    } else {
      tree1.merge(u, v);
    }
  }
  for (long long int i = (0), i_end_ = (N); i < i_end_; ++i) {
    {
      long long int sz = tree0.size(i);
      ans += sz - 1;
    }
    {
      long long int sz = tree1.size(i);
      ans += sz - 1;
    }
    ans +=
        ((long long int)tree0.size(i) - 1) * ((long long int)tree1.size(i) - 1);
  }
  cout << ans << '\n';
}
