SP11540 TRAIN07 - Training

Mirko 和 Slavko 正在为克罗地亚一年一度的双人自行车马拉松比赛刻苦训练。他们需要选择一条适合的路线进行训练。 在他们的国家里，有 $N$ 座城市和 $M$ 条道路。每条道路都连接两座城市，且可以双向通行。

第一行输入两个整数 $N$ 和 $M$，满足 $2 \le N \le 1000$，$1 \le M \le 5000$。 接下来的 $M$ 行中，每行有三个整数 $A$、$B$ 和 $C$，分别表示城市 $A$ 和城市 $B$ 之间有一条道路，且通行成本为 $C$，其中 $1 \le A, B \le N$，$1 \le C \le 1000$。 每座城市最多能连接 10 条道路。任意两个城市之间最多只能有一条直接连接的道路。

输出一个整数，表示按照题目要求选择的路径的最小总成本。 **本翻译由 AI 自动生成**