1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<string> 7 #include<iomanip> 8 #include<cmath> 9 using namespace std;10 #define LL long long11 const int maxn=1003000;12 int n;13 struct node{14     int y,next,v;15 }e[maxn<<1];16 int linkk[maxn],len=0,siz[maxn],q[maxn],tail=0,fa[maxn],t[maxn],top=0,ru[maxn],w[maxn];17 LL ans=0;18 void insert(int x,int y,int v){19     e[++len].y=y;20     e[len].next=linkk[x];21     e[len].v=v;22     linkk[x]=len;23 }24 void init(){25     scanf("%d",&n);26     int x,y,v;27     for(int i=1;i<n;i++){28         scanf("%d%d%d",&x,&y,&v);29         insert(x,y,v);insert(y,x,v);30     }31 }32 void bfs(){33     q[++tail]=1;int x;34     for(int head=1;head<=tail;head++){35         x=q[head];36         for(int i=linkk[x];i;i=e[i].next){37             if(e[i].y==fa[x])continue;38             q[++tail]=e[i].y;39             fa[e[i].y]=x;40             ru[x]++;41             w[e[i].y]=e[i].v;42         }43         if(!ru[x])t[++top]=x;44     }45     for(int head=1;head<=top;head++){46         x=t[head];siz[x]++;47         siz[fa[x]]+=siz[x];48         ru[fa[x]]--;49         if(!ru[fa[x]])t[++top]=fa[x];50         ans+=(LL)abs(n-2*siz[x])*(LL)w[x];51     }52 }53 void work(){54     bfs();55     cout<<ans<<endl;56 }57 int main(){58     freopen("1.in","r",stdin);59     freopen("1.out","w",stdout);60     init();61     work();62 }