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;
vector<pair<int, int>> adjacency[200010];
int parent[200010];
long long dp[5][200010];
void dfs(int v) {
  if (v && adjacency[v].size() == 1) return;
  for (auto childPair : adjacency[v]) {
    int child = childPair.first;
    int edge = childPair.second;
    if (v && parent[v] == child) continue;
    parent[child] = v;
    dfs(child);
    dp[0][v] += dp[0][child];
    if (edge) {
      dp[1][v] += dp[1][child] + 1;
      dp[3][v] += dp[3][child] + dp[4][child];
    } else {
      dp[2][v] += dp[1][child] + dp[2][child];
      dp[4][v] += dp[4][child] + 1;
    }
  }
  dp[0][v] += 2 * dp[1][v] + dp[2][v] + dp[3][v] + 2 * dp[4][v];
  long long lca = 0;
  for (auto childPair : adjacency[v]) {
    int child = childPair.first;
    int edge = childPair.second;
    if (v && parent[v] == child) continue;
    if (edge) {
      lca += (dp[1][child] + dp[3][child] + dp[4][child] + 1) *
             (dp[1][v] - (dp[1][child] + 1));
    } else {
      lca += (dp[4][child] + 1) *
             (dp[1][v] + dp[2][v] + dp[4][v] -
              (dp[1][child] + dp[2][child] + dp[4][child] + 1));
    }
  }
  dp[0][v] += lca;
}
int main(void) {
  int N;
  cin >> N;
  for (int i = 1; i < N; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    x--;
    y--;
    adjacency[x].push_back(make_pair(y, c));
    adjacency[y].push_back(make_pair(x, c));
  }
  dfs(0);
  cout << dp[0][0] << endl;
  return 0;
}
