该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

总所周知日轮刀是鬼杀队最重要的东西。现在锻刀村锻造好了一批日轮刀，村中跑得最快的钢铁速奉命要把这批刀送到鬼杀队队员的手中，锻刀村在节点 $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$，输入保证任意两点都能互相到达。