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 <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#ifdef __GNUC__
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T n){int cnt=0;while(n){if(n%2)cnt++;n/=2;}return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
  vector<string> res;
  for(int i=0,s=0;i<SIZE(str);i++){
    if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
    else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
  }
  return res;
}

class UnionFindTree{
private:
  // indexの数の親ノード(ある集合の親を見つけたいときはここを直接参照せず、findを使う)
  vector<int> par;
  // indexを根とする木のランク
  vector<int> rank;
  // 集合のサイズ
  vector<int> cnts;
  // 木の最大値
  int treeSize;
public:
  UnionFindTree(int initTreeSize = 1000){
    // 引数で与えられた値を最大格納数とするUnionFindTreeの作成
    treeSize = initTreeSize;
    init();
  }
  void init(){
    for(int i = 0; i < treeSize; i++){
      par.push_back(i);
      rank.push_back(0);
      cnts.push_back(1);
    }
  }
  // 与えられた数が格納されている木のルートを探索
  int find(int x){  
    if(par[x] == x)return x;
    else return par[x] = find(par[x]);
  }
  // 和集合をとる。ただしここでは各集合の親の付け替えは起こらない
  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(rank[x] < rank[y]){
      par[x] = y;
      cnts[y]+=cnts[x];
    }
    else{
      par[y] = x;
      cnts[x]+=cnts[y];
      if(rank[y] == rank[x])rank[x]++;
    }
  }
  // xの属する集合のサイズ
  int getCnt(int x){
    return cnts[find(x)];
  }
  bool same(int x,int y){
    return find(x) == find(y);
  }
    
};

typedef pair<int,pii> pip;
int N;
int AS[1000001];
int BS[1000001];
int CS[1000001];
int main(){
  fastStream();
  cin>>N;
  vector<pip> v;
  for(int i=0;i<N-1;i++){
    cin>>AS[i]>>BS[i]>>CS[i];
    v.push_back(pip(CS[i],pii(AS[i],BS[i])));
  }
  sort(v.begin(),v.end());
  UnionFindTree uft(N+1);
  ll res=0;
  for(int i=0;i<N-1;i++){
    ll a=uft.getCnt(v[i].second.first);
    ll b=uft.getCnt(v[i].second.second);
    res+=a*b*v[i].first;
    uft.unite(v[i].second.first,v[i].second.second);
  }
  cout<<res<<endl;
  
  return 0;
}