6408: 洛谷P1629 - 邮递员送信
[Creator : ]
Description
有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$。
由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。
这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。
由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。
这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。
Input
第一行包括两个整数，$n,m$，表示城市的节点数量和道路数量。
第二行到第 $m+1$ 行，每行三个整数，$u,v,w$，表示从 $u$ 到 $v$ 有一条通过时间为 $w$ 的道路。
第二行到第 $m+1$ 行，每行三个整数，$u,v,w$，表示从 $u$ 到 $v$ 有一条通过时间为 $w$ 的道路。
Output
输出仅一行，包含一个整数，为最少需要的时间。
Constraints
对于 $30\%$ 的数据，$1 \leq n \leq 200$。
对于 $100\%$ 的数据，$1 \leq n \leq 10^3, 1 \leq m \leq 10^5, 1\leq u,v \leq n, 1 \leq w \leq 10^4$。
输入保证任意两点都能互相到达。
对于 $100\%$ 的数据，$1 \leq n \leq 10^3, 1 \leq m \leq 10^5, 1\leq u,v \leq n, 1 \leq w \leq 10^4$。
输入保证任意两点都能互相到达。
Sample 1 Input
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
Sample 1 Output
83