开会

题目描述

Orange是一家大型联合企业的CEO，这家企业有 $n$ 个分部遍布在全国的各个不同城市，这些城市之间由 $m$ 条双向道路连通，每条道路都需要一定的过路费 $w$。作为CEO的Orange最近要下达一项重大的决策，于是他想选择一家企业分部作为开会的地点，邀请所有分部的负责人共聚于此，商议这一项重要的决策。

我们都知道，公务出差是要报销路费的，因此Orange需要给来开会的各位负责人报销路费。我们记开会地点为 $P$，则每个人需要报销的费用为其所在的城市 $u_i$ 到开会地点 $P$ 的最小过路费之和，而Orange最后需要报销的费用是所有人的报销费用之和。为了让费用尽可能的少，Orange想让你编写一个程序，计算选择哪个城市作为开会地点时，报销总费用最小，其为多少？

输入格式

第一行为两个整数 $n$，$m$，表示企业分部总数和连接他们所在城市的道路数量。 接下来每行三个整数 $u, v, w$，表示 $u, v$ 之间存在一条双向道路，它的过路费为 $w$。

数据范围: $1 \le n \le 800$ $1 \le m \le 1500$ $1 \le w \le 1000$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

10

提示

选择 $1$ 号城市作为开会地点是最好的。