Problem: You are involved in the development of a certain game. The game is for players to explore randomly generated dungeons. As a specification of the game, I want to show the player the danger level of the dungeon in advance and select whether to search for the generated dungeon or to regenerate a new dungeon.

There are n rooms in the dungeon generated by this game, and they are numbered from 0 to n-1. The rooms are connected by a passage. There are a total of n-1 passages connecting rooms. The passage can go in either direction. In addition, a distance is set between the rooms. In the generated dungeon, it is possible to go from one room to all other rooms via several passages. Then, when the player plays the game, two different rooms are selected as the start point and the goal point.

You decide to decide how to evaluate the risk in order to evaluate the dungeon. First, the risk level when moving from one room to another is set to the value of the most costly passage among the passages used to move between rooms in the shortest time. Then, we decided to set the risk level of the dungeon as the sum of the risk levels when moving between a pair of rooms where i <j.

A randomly generated dungeon is given as input. First, calculate the risk of moving for all room pairs where i <j. Then output the sum as the answer to the problem.



Input

The input is given in the following format.


n
a1 b1 c1
..
..
..
an-1 bn-1 cn-1


ai bi ci means that the distance of the passage connecting the rooms ai and bi is ci.

Input meets the following constraints
2 ≤ n ≤ 200,000
0 ≤ ai, bi <n
0 ≤ ci ≤ 100,000

Output

Print the answer value on one line

Examples

Input

4
0 1 3
1 2 5
1 3 2


Output

23


Input

6
0 2 5
2 1 1
2 3 10
3 5 4
3 4 2


Output

111

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>
#ifndef LIB_REPEAT_HPP
#define LIB_REPEAT_HPP
#define repeat(i,n) for (int i = 0; i < (n); ++i)
#define repeat_from(i,m,n) for (int i = (m); i < (n); ++i)
#define repeat_one(i,n) for (int i = 1; i <= (n); ++i)
#define repeat_rev(i,n) for (int i = (n)-1; 0 <= i; --i)
#define foreach(it, cont) for (decltype(cont.begin()) it = cont.begin(); it != cont.end(); ++it)
#endif
#include <vector>

struct union_find {
    std::vector<int> tree;
    union_find(size_t n) : tree(n, -1) {}
    bool is_root(int a) { return tree[a] < 0; }
    int find_root(int a) { return is_root(a) ? a : (tree[a] = find_root(tree[a])); }
    int tree_size(int a) { return - tree[find_root(a)]; }
    void union_tree(int a, int b) {
        a = find_root(a); b = find_root(b);
        if (a != b) {
            if (not (tree_size(a) < tree_size(b))) std::swap(a,b);
            tree[b] += tree[a];
            tree[a] = b;
        }
    }
    bool is_connected(int a, int b) { return find_root(a) == find_root(b); }
};
#ifndef LIB_TYPEDEF_LL_HPP
#define LIB_TYPEDEF_LL_HPP
typedef long long ll;
typedef unsigned long long ull;
#endif
using namespace std;
struct edge { int a, b; ll c; };
bool operator < (const edge & x, const edge & y) { return x.c > y.c; } // reversed
int main() {
    ios_base::sync_with_stdio(false);
    int N; cin >> N;
    priority_queue<edge> que;
    repeat (i,N-1) {
        int a, b; ll c; cin >> a >> b >> c;
        que.push((edge){ a,b,c });
    }
    ll result = 0;
    union_find uft(N);
    while (not que.empty()) {
        const edge e = que.top(); que.pop();
        result += (ll)uft.tree_size(e.a) * (ll)uft.tree_size(e.b) * e.c;
        uft.union_tree(e.a, e.b);
    }
    cout << result << endl;
    return 0;
}