描述

在一个距离地球几亿光年的星球上，有\(n\)个国家。为了使国家繁荣富强，国王们希望通过修建道路使国家之间相互连通，促进贸易往来。但是国王们都不太大方，所以他们只准备修建\(n-1\)条道路使每个国家恰好连通。
这个星球上的人们欣赏对称美，两边国家数量不对称使他们感到烦躁，需要更多的人力物力，所以一条道路的修建费用等于道路长度乘以道路两端的国家个数之差的绝对值。
由于星球上的人普遍数学不好，所以他们费劲心思终于请到了作为外星人的你帮忙计算修建道路的总费用。

格式

输入格式

输入的第一行包含一个整数\(n\)，表示这个星球上的国家的数量，国家从\(1\)到\(n\)编号。
接下来\(n–1\)行描述道路建设情况，其中第\(i\)行包含三个整数\(a_i\)、\(b_i\)和\(c_i\)，表示第\(i\)条双向道路修建在\(a_i\)与\(b_i\)两个国家之间，长度为\(c_i\)（\(1 \leq c_i \leq 10000\)）。

输出格式

输出一个整数，表示修建所有道路所需要的总费用。

样例1

样例输入1

6 
1 2 1 
1 3 1 
1 4 2 
6 3 1 
5 2 1 

样例输出1

20 

限制

2s,256MB
对于30%的数据，保证\(1 \leq n \leq 5000\)。
对于100%的数据，保证\(1 \leq n \leq 10^6\)。