题目描述

Syrup 是一只生活在城镇中的乌龟，这个城镇包含 $N$ 个地点和 $M$ 条双向道路。每个地点从 $1$ 到 $N$ 编号，每条道路从 $1$ 到 $M$ 编号。第 $i$ 条道路直接连接地点 $A_i$ 和 $B_i$，长度为 $W_i$，可以双向通行。所有地点通过这些道路直接或间接连通，且没有两条道路共享相同的端点。

城镇的居民根据道路的美观性进行了排序，道路编号越大，美观性越高。现在，居民们计划将一条美观性更高的道路复制到一条美观性更低的道路上。这将使得美观性较低的道路长度增加，同时保留原有道路的其他属性。具体来说，如果道路 $j$ 被复制到道路 $i$，需要满足 $i < j$，且复制后道路 $i$ 的长度变为 $W_i + W_j$。

Syrup 通常从他的家（地点 $N$）前往主广场（地点 $1$）。他希望知道在完成上述项目后，从地点 $1$ 到地点 $N$ 的最短路径长度可能达到的最大值。

输入格式

• 第一行包含两个整数 $N$ 和 $M$，分别表示地点数量和道路数量。
• 接下来的 $M$ 行中，每行包含三个整数 $A_i, B_i, W_i$，描述一条道路。

输出格式

输出一个整数，表示在完成项目后，从地点 $1$ 到地点 $N$ 的最短路径长度的最大值。

6 8
5 6 2
3 1 4
1 2 2
6 2 3
5 3 3
3 2 1
4 6 3
2 4 2

8

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

3

7 6
2 1 4
1 3 3
4 5 4
5 7 3
4 6 2
1 4 0

10

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

8

提示

【数据范围】

• $3 \leq N \leq 300,000$
• $2 \leq M \leq 300,000$
• $1 \leq A_i, B_i \leq N$ 且 $A_i \neq B_i$
• $0 \leq W_i \leq 10^9$