题目描述

徐老师有一棵包含 $n$ 个节点的树

现在徐老师想求出一个关于 $1$ 到 $n$ 的排列 $p_1, p_2, \cdots , p_n$

使得 $\sum_{i=1}^{n}dis(i,p_i)$ 的值最大

其中 $dis(i,p_i)$ 表示节点 $i$ 和节点 $p_i$ 在树上的距离

请你帮徐老师完成这个任务

输入格式

第一行包含一个整数 $n$ 。

接下来 $n-1$ 行每行包含三个整数 $u, v, x$，表示节点 $u$ 和节点 $v$ 之间存在一条长度为 $x$ 的边。

输出格式

对于每组测试数据，输出一个整数。

数据范围

对于 $100\%$ 的数据，$2 \leq n\leq 1000000,0<$ 边权 $\leq 1000$。

样例输入

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

样例输出

30