题目描述

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

输入格式

第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。 第二行到第 (m+1) 行，每行三个整数，u,v,w，表示从 u 到 v 有一条通过时间为 w 的道路。

输出格式

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

样例

输入样例 1

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

输出样例 1

83

输入样例 2

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

输出样例 2

14

输入样例 3

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

输出样例 3

18

提示

数据规模：1≤n≤10^3，1≤m≤10^5，1≤u,v≤n，1≤w≤10^4，输入保证任意两点都能互相到达。

思路：两次应用 Dijkstra 算法。 正向建图求1到各点的最短路径； 反向建图（f开头）求各点到1的最短路径。