J13 习题-3 邮递员送信

题目描述

有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $N-1$ 样东西，其目的地分别是 $2～N$。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $M$ 条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这 $N-1$ 样东西并且最终回到邮局最少需要多少时间。

输入格式

输入文件第一行包含两个正整数 $N$ 和 $M$； 接下来 $M$ 行，每行三个正整数 $U$、$V$、$W$，表示该条道路为从 $U$ 到 $V$ 的，且通过这条道路需要 $W$ 的时间。 输入保证任意两点都能互相到达。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

输入样例

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

输出样例

83

样例分析

如上所述。

数据范围

对于 $30\%$ 的数据：$1 \leq N \leq 200$； 对于 $100\%$ 的数据： $1 \leq N \leq 1,000$， $1\leq M \leq 100,000$，$1 \leq U \neq V \leq N$，$1 \leq W \leq 10,000$。