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;
const int N = (int)2e5 + 500;
vector<pair<int, int> > g[N];
int n, sz[N];
long long dp[3][3], ans;
bool used[N];
void sizes(int v, int p) {
  sz[v] = 1;
  for (auto u : g[v]) {
    if (u.first == p || used[u.first]) continue;
    sizes(u.first, v);
    sz[v] += sz[u.first];
  }
}
int centroid(int v, int p, int sz_comp) {
  for (auto u : g[v])
    if (u.first != p && !used[u.first] && sz[u.first] > sz_comp / 2)
      return centroid(u.first, v, sz_comp);
  return v;
}
void dfs1(int v, int p, int f, int e) {
  ans++;
  if (f == e) ans++;
  if (f == 0 && e == 0) ans += 2 * dp[0][0] + dp[0][1] + dp[1][1];
  if (f == 0 && e == 1) ans += dp[0][0];
  if (f == 1 && e == 0) ans += dp[1][1];
  if (f == 1 && e == 1) ans += 2 * dp[1][1] + dp[0][0] + dp[1][0];
  for (auto u : g[v]) {
    if (u.first == p || used[u.first]) continue;
    if (f < e && u.second < e) continue;
    if (f > e && u.second > e) continue;
    dfs1(u.first, v, f, u.second);
  }
}
void dfs2(int v, int p, int f, int e) {
  dp[f][e]++;
  for (auto u : g[v]) {
    if (u.first == p || used[u.first]) continue;
    if (f < e && u.second < e) continue;
    if (f > e && u.second > e) continue;
    dfs2(u.first, v, f, u.second);
  }
}
void solve(int v) {
  sizes(v, v);
  dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
  v = centroid(v, v, sz[v]);
  for (auto u : g[v]) {
    if (used[u.first]) continue;
    dfs1(u.first, v, u.second, u.second);
    dfs2(u.first, v, u.second, u.second);
  }
  used[v] = 1;
  for (auto u : g[v])
    if (!used[u.first]) solve(u.first);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, z;
    cin >> u >> v >> z;
    g[u].push_back({v, z});
    g[v].push_back({u, z});
  }
  solve(1);
  cout << ans;
}
