有一个邮递员要送东西，邮局在节点 $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

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131072\mathrm{KB}$
• 对于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$