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>
#pragma GCC optimize("-O2")
using namespace std;
void err(istream_iterator<string> it) { cerr << endl; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\t";
  err(++it, args...);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& c, pair<T1, T2>& v) {
  c << "(" << v.first << "," << v.second << ")";
  return c;
}
template <template <class...> class TT, class... T>
ostream& operator<<(ostream& out, TT<T...>& c) {
  out << "{ ";
  for (auto& x : c) out << x << " ";
  out << "}";
  return out;
}
const int LIM = 2e5 + 5, MOD = 1e9 + 7;
const long double EPS = 1e-9;
int n;
vector<pair<int, int> > adj[LIM];
long long dp[LIM][2];
long long dpu[LIM][2];
int visited[LIM];
void bfsdown(int node) {
  visited[node] = 1;
  for (auto& r : adj[node]) {
    if (visited[r.first]) continue;
    bfsdown(r.first);
    if (adj[r.first].size() == 1 && r.first != 0) {
      dp[node][r.second]++;
      continue;
    }
    if (r.second == 1) {
      dp[node][1] += 1 + dp[r.first][1];
    } else if (r.second == 0) {
      dp[node][0] += 1 + dp[r.first][1] + dp[r.first][0];
    }
  }
}
void bfsup(int node, int p, bool c) {
  visited[node] = 1;
  if (c == 0) {
    dpu[node][0] += (dpu[p][0] + dpu[p][1] + dp[p][0] + dp[p][1] - dp[node][0] -
                     dp[node][1]);
  } else {
    dpu[node][1] += (dpu[p][1] + dp[p][1] - dp[node][1]);
  }
  for (auto& r : adj[node]) {
    if (visited[r.first]) continue;
    bfsup(r.first, node, r.second);
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    x--;
    y--;
    adj[x].push_back(make_pair(y, c));
    adj[y].push_back(make_pair(x, c));
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 2; ++j) dp[i][j] = 0;
  }
  bfsdown(0);
  for (int i = 0; i < n; ++i) visited[i] = 0;
  visited[0] = 1;
  for (auto& r : adj[0]) {
    bfsup(r.first, 0, r.second);
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 2; ++j) {
      ans += dp[i][j];
      ans += dpu[i][j];
    }
  }
  cout << ans << '\n';
  return 0;
}
