对于完全图 $G$，若有且仅有一棵最小生成树为 $T$，则称完全图 $G$ 是树 $T$ 扩展出的。

给你一棵树 $T$，找出 $T$ 能扩展出的边权和最小的完全图 $G$。

第一行 $N$ 表示树 $T$ 的点数；

接下来 $N-1$ 行三个整数 Si,Ti,DiS_i, T_i, D_iSi,Ti,Di；描述一条边（Si,TiS_i, T_iSi,Ti）权值为 DiD_iDi；

保证输入数据构成一棵树。

样例说明

添加 $D(2,3)=2,D(3,4)=3,D(2,4)=3$ 即可。

对于 $20\%$ 的数据，$N\le 10$；
对于 $50\%$ 的数据，$N\le 1000$；
对于 $100\%$ 的数据，N≤105,1≤Di≤105N\le 10^5, 1\le D_i\le 10^5N≤10⁵,1≤Di≤10⁵。