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<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>
#include<tuple>


using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };

#define ARRAY_MAX 100005 

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

typedef tuple<int, int, int> tpl;

//繋げる方向を一方向にする
typedef struct union_find {

	vector<ll> pa;//親
	vector<ll> ra;//木の深さ
	vector<ll> siz;
	//n要素で初期化
	void init(ll n) {
		pa.resize(n);
		ra.resize(n);
		siz.resize(n);
		for (ll i = 0; i < n; i++) {
			pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
			ra[i] = 0LL;/*各ノード自体の高さは0*/
			siz[i] = 1LL;
		}
	}
	//木の根を求める
	ll find(ll x) {
		if (pa[x] == x) {
			return x;/*根ならそのノードの番号を返す*/
		}
		else {
			return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
		}
	}

	//xとyの属する集合を併合する
	void unite(ll x, ll y) {
		x = find(x);//xの根の番号を探す
		y = find(y);//yの根の番号を探す
		if (x == y) {//一致すればつながっている
			return;
		}
		pa[y] = x;
		siz[x] += siz[y];
	}

	//xとyが同じ集合に属するか判定
	bool same(ll x, ll y) {
		return find(x) == find(y);//同じ集合なら1、違うなら0が返る
	}
}UF;

int main() {

	ll n;
	cin >> n;
	vector<tpl> vec(n-1);
	for (int i = 0; i < n-1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		vec[i] = tpl(c, a, b);
	}

	UF tree;
	tree.init(n);
	
	sort(vec.begin(), vec.end());

	ll ans = 0;

	for (int i = 0; i < n-1; i++)
	{
		ll a, b, c;
		tie(c, a, b) = vec[i];
		a = tree.find(a);
		b = tree.find(b);
		if (!tree.same(a, b))
		{
			ans += 1LL * c * tree.siz[a] * tree.siz[b];
			tree.unite(a, b);
		}
	}
	cout << ans << endl;
}