题目描述

sxy环球旅行结束后，上任Floyd-Warshall市市长。没几天就接到大量的投诉信抱怨城市电力供应不足。于是sxy决定建核电站来解决电力供应不足的问题。由于经费原因，sxy只能建一座核电站，他视察了整个城市后选出了几个比较合适的地点，从中选出一个地点，建核电站，其余的合适的地点建上变电站。大家都希望建立的核电站能够到所有的变电站的距离之和最小的情况下，使得核电站到每个变电站的最短距离之和最小，电线就沿着这样的最短距离之和最小的道路铺设，这样用比较少的电线，节省经费，也便于维护。

输入格式

第一行，两个整数 $n,m$ 。表示sxy共选出了 $n$ 个地点，这 $n$ 个地点之间共有 $m$ 条道路。

下面 $m$ 行，每行 $3$ 个整数，$u,v,t$ ，表示从第 $u$ 个地点到第 $v$ 个地点，有一条长度为 $t$ 的双向的道路。

输出格式

输出一行，一个整数，表示最短的总共的电线长度

样例

样例输入

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

样例输出

6

数据范围与提示

最短的总共的电线长度 $ans =$ 从 $3$ 号点出发到其余各个点的路径和，即 $2+3+1 = 6$

数据范围

• $1 <= n <= m <= 500$

• $1 <= c <= 1000$

良心数据！！！

数据已修复，并附赠题面改善及重新评测。