为了吸引更多游客，国家公园的经理打算在“热门步道”的两侧种植花卉，所谓热门步道是指普通游客所使用的步道。普通游客只会通过最短路径从公园入口前往最高峰，那里有令人叹为观止的景色。因此，他想知道需要多少米长的花卉来实现他的想法。

例如，在图中所示的公园地图中，普通游客只会走以下三条路径中的某一条（这些都是从入口到最高峰的最短路径）：

• 在入口处，一些人走最右侧的步道到达兴趣点 3（100 米），直接前往点 7（200 米），然后选择直接通往最高峰的步道（620 米）。
• 其他人从入口向左走，到达点 1（580 米）。然后，他们选择通往点 4 的两条步道中的任意一条（两条步道均为 90 米）。在点 4，他们沿着直接通往最高峰的步道走（250 米）。

请注意，热门步道（即普通游客所走的步道）在图中以黄色高亮显示。由于这些步道长度之和为 1930 米，因此覆盖热门步道两侧所需的花卉长度为 3860 米（$3860 = 2 \times 1930$）。

任务

给定公园的描述，包括其兴趣点和（双向）步道，目标是找出覆盖热门步道两侧所需的花卉长度。保证对于给定的输入，从公园入口到最高峰一定存在路径。

输入格式

输入的第一行包含两个整数：$P$ 和 $T$。$P$ 是兴趣点的数量，$T$ 是步道的数量。点由 $0$ 到 $P-1$ 的整数标识。入口点为 $0$，最高峰为点 $P-1$。

接下来的 $T$ 行，每行描述一条不同的步道。每行包含三个整数 $p_1$、$p_2$ 和 $l$，表示该（双向）步道直接连接点 $p_1$ 和 $p_2$（不一定不同），长度为 $l$（单位为米）。

同一行中的整数由单个空格分隔。

数据范围

$2 \le P \le 10\,000$ 点的数量。 $1 \le T \le 250\,000$ 步道的数量。 $1 \le l \le 1\,000$ 步道的长度。

输出格式

输出一行，表示覆盖热门步道两侧所需的花卉长度（单位为米）。

样例

样例输入 1

10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160

样例输出 1

3860

样例输入 2

4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1

样例输出 2

18