题目描述

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

输入格式

第一行包括两个整数，$n$ 和 $m$，表示城市的节点数量和道路数量。

第二行到第 $(m+1)$ 行，每行三个整数，$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 10^3$，$1 \leq m \leq 10^5$，$1\leq u,v \leq n$，$1 \leq w \leq 10^4$，输入保证任意两点都能互相到达。

8 39
1 2 33
2 1 11
2 3 22
3 2 23
3 4 74
4 3 59
4 5 49
5 4 70
5 6 41
6 5 8
6 7 89
7 6 30
7 8 93
8 7 57
5 8 5058
1 4 4593
5 7 3291
5 5 7520
8 7 4860
7 4 6726
1 2 4447
3 3 4066
5 7 1322
5 6 1957
7 3 6359
8 4 7697
8 2 9048
5 8 6612
4 4 2699
2 6 1973
6 2 1499
8 4 9375
7 7 6458
8 7 9925
5 1 746
8 3 7433
3 6 9308
3 8 1768
8 4 9171

2254

11 60
1 2 96
2 1 52
2 3 3
3 2 76
3 4 28
4 3 22
4 5 80
5 4 62
5 6 42
6 5 92
6 7 91
7 6 31
7 8 22
8 7 21
8 9 65
9 8 79
9 10 80
10 9 53
10 11 40
11 10 8
4 6 6903
11 9 4361
11 1 2544
3 8 9378
10 9 8121
11 10 1618
8 7 5898
11 6 9359
6 11 8311
1 7 7581
5 4 6165
8 11 4041
4 5 2273
11 3 3542
7 11 2208
1 10 8295
11 3 5917
6 10 1484
1 2 6821
6 4 4713
4 3 3521
4 5 9238
1 2 700
11 10 8636
5 10 8889
11 2 1090
11 11 4983
7 4 5576
5 6 1275
8 7 6873
11 4 6796
1 9 2550
5 4 2107
2 3 5366
9 8 2707
3 6 3584
7 7 7677
4 4 1329
3 11 4940
9 9 8245

5917