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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
   
using namespace std;
   

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define rforeach(it, c) for (__typeof__((c).rbegin()) it=(c).rbegin(); it != (c).rend(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))
#define COPY(dest, src) memcpy(dest, src, sizeof(dest))
#define ten(n) ((long long)(1e##n))
#define bin(n) (1LL << (n))

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

template <class T> void sort(vector<T>& c) { sort(c.begin(), c.end()); }
template <class T> void uniq(vector<T>& c) { sort(c.begin(), c.end()); c.erase(unique(c.begin(), c.end()), c.end()); }

template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
  
template <class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p) { os << "( " << p.first << ", " << p.second << " )"; return os; }
  
template <class T> void print(T a, int n, const string& deli = " ", int br = 1) { for (int i = 0; i < n; ++i) { cout << a[i]; if (i + 1 != n) cout << deli; } while (br--) cout << endl; }
template <class T> void print(const T& c, const string& deli = " ", int br = 1) { foreach (it, c) { cout << *it; if (++it != c.end()) cout << deli;--it; } while (br--) cout << endl; }
template <class T> void print2d(T a, int w, int h, int width = -1, int br = 1) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) {    if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
   
template <class T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
template <class T> void input(T* a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }

void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
#define trace(x) (cout << #x << ": " << (x) << endl)

bool valid(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }


typedef long long ll;
typedef pair<int, int> pint;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
  
const double PI = acos(-1.0);
const int mod = 1000000007;



class UnionFind
{
private:
    vector<int> data;
public:
    int n;
    int groups;
    UnionFind(int n) : data(n, -1), n(n), groups(n) { }

    void unite(int x, int y)
    {
        x = root(x), y = root(y);
        if (x != y)
        {
            --groups;
            if (data[x] > data[y])
                swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
};
struct E
{
    int a, b, c;
    bool operator<(const E& e) const
    {
        return c < e.c;
    }
};
int main()
{
    fast_io();

    int n;
    static E e[2 * ten(5) + 100];
    cin >> n;
    rep(i, n - 1)
        cin >> e[i].a >> e[i].b >> e[i].c;
    sort(e, e + (n - 1));

    ll res = 0;
    UnionFind uf(n);
    rep(i, n - 1)
    {
        ll num_pair = (ll)uf.size(e[i].a) * uf.size(e[i].b);
        res += num_pair * e[i].c;
        uf.unite(e[i].a, e[i].b);
    }
    cout << res << endl;
}