乌龟 Syrup 居住在一个由 $N$ 个地点和 $M$ 个道路连接的城镇中。每个地点的编号为 $1, 2, \dots, N$，每条道路的编号为 $1, 2, \dots, M$。第 $i$ 条道路直接连接地点 $A_i$ 和 $B_i$，长度为 $W_i$ 单位，且可以双向通行。这些道路和地点满足：任意两个地点之间都可以直接或间接到达，且没有两条道路拥有完全相同的两个端点（即无重边）。

每条道路都有其独特的风景，镇上的居民早已对每条道路的观赏性（美学价值）达成了共识。目前的道路编号顺序就反映了这一点：从 $1$ 到 $M$，道路的观赏性依次递增。

最近，居民们希望进一步提升城镇地形的吸引力。在权衡了该任务的许多实用性和美学因素后，他们达成了一个令人难以置信的折中方案——在一条观赏性严格较低的道路的路径上，建造一条与另一条观赏性较高的道路完全相同的复制品。这一操作适用于任意一对道路，它会将观赏性较低的道路的长度增加观赏性较高的道路的长度。换句话说，当且仅当 $i < j$ 时，道路 $j$ 可以被复制到道路 $i$ 中，这样做会将道路 $i$ 的长度变为 $W_i + W_j$。现在，唯一剩下的工作就是投票选出实际用于该项目的一对道路。

Syrup 经常在位于地点 $N$ 的家和位于地点 $1$ 的主广场之间往返。他想提前知道，在项目完成后，这两个地点之间的最短距离最大可能达到多少。你的任务是确定这个最大可能的最短距离。

输入格式

输入从标准输入读入。

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行包含三个整数 $A_i$、$B_i$ 和 $W_i$，描述一条道路。

输出格式

输出到标准输出。

输出应在单行中包含一个整数，表示项目实施后，地点 $1$ 和 $N$ 之间最短路径的最大可能长度。

实现细节

由于子任务 3、4、5、6 和 7 的输入规模可能非常大，建议您使用带有快速输入输出的 C++ 来解决此问题。科学委员会没有能够完全解决此问题的 Python 语言解法。

附件中提供了包含快速输入/输出模板的 C++ 和 Java 源文件。强烈建议您使用这些模板。

如果您使用 Java 实现解决方案，请将文件命名为 Aesthetic.java，并将主函数放在 Aesthetic 类中。

子任务

每个测试点的最大运行时间为 2.0s，最大内存使用量为 1GiB。

对于所有测试用例，输入将满足以下范围：

• $3 \le N \le 300\,000$
• $2 \le M \le 300\,000$
• $1 \le A_i \ne B_i \le N$
• $0 \le W_i \le 10^9$

您的程序将在满足以下限制的输入实例上进行测试：

样例

输入样例 1

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

输出样例 1

8

说明 1

该测试用例适用于子任务 1、2、6 和 7。

地点 1 和 6 之间的最短路径最初为 $1 \to 2 \to 6$，长度为 5。如果用蓝色标记的道路 3 恰好被任意一条长度为 3 且观赏性更高的道路延长，则最短路径的长度可能会增加到 8，如红色标记所示。

输入样例 2

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

输出样例 2

3

说明 2

该测试用例适用于子任务 1、2、5、6 和 7。

对于该测试用例，可以证明，用观赏性较高的道路延长观赏性较低的道路，永远不会使最短路径的长度超过其原始值 3。

输入样例 3

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

输出样例 3

10

说明 3

该测试用例适用于子任务 1、2、3、6 和 7。

输入样例 4

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

输出样例 4

8

说明 4

该测试用例适用于子任务 1、2、4、6 和 7。