[AdditionalFile5246.zip](file://AdditionalFile5246.zip?type=additional_file)

#5246. 「NOISG 2020 Final」Aesthetic

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2020 Final T5. Aesthetic

乌龟西拉普生活在一个由 $N$ 个地点和 $M$ 条道路连接构成的小镇。每个地点编号为 $1, 2, \ldots, N$，每条道路编号为 $1, 2, \ldots, M$。第 $i$ 条道路直接连接地点 $A_i$ 和 $B_i$，长度为 $W_i$ 单位，且可双向通行。这些道路和地点排列方式保证任意两个地点之间可通过直接或间接方式到达，且任意两条道路的端点不同。

每条道路拥有独特的风景，小镇居民早已就每条道路的旅行美学程度达成共识。当前道路的编号顺序反映了这一点：从 $1$ 到 $M$，道路的美学程度递增。

最近，居民们希望进一步提升小镇地形的吸引力。在权衡了众多功能和美学因素后，他们达成了一个令人惊叹的折衷方案：在一条美学程度较低的道路路径上，建造一条美学程度更高的道路的完全相同副本。这一操作可应用于任意一对道路，且会将较不美观的道路长度延长为更美观道路的长度。换句话说，若 $i < j$，可以将道路 $j$ 复制到道路 $i$ 上，这会将道路 $i$ 的长度改为 $W_i + W_j$。现在，只需通过投票选出一对道路来实施这个项目。

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

输入格式

程序需从标准输入读取数据。

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

接下来的 $M$ 行，每行包含三个整数 $A_i, B_i, W_i$，描述一条道路。

输出格式

程序需向标准输出输出结果。

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

样例 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

输出

8

地点 $1$ 和 $6$ 之间的初始最短路径为 $1 \to 2 \to 6$，长度为 $5$。如果编号为 $3$ 的道路（标记为蓝色）被任意一条长度为 $3$ 的更美观道路延长，最短路径的长度可能增加到 $8$（标记为红色）。

这个样例满足子任务 $1, 2, 6, 7$ 的限制。

样例 2

输入

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

输出

3

对于这个样例，可以证明将一条美学程度较低的道路延长为一条更美观的道路，不会使最短路径的长度超过其初始值 $3$。

这个样例满足子任务 $1, 2, 5, 6, 7$ 的限制。

样例 3

输入

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

输出

10

这个样例满足子任务 $1, 2, 3, 6, 7$ 的限制。

样例 4

输入

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

输出

8

这个样例满足子任务 $1, 2, 4, 6, 7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $3 \leq N \leq 300000$
• $2 \leq M \leq 300000$
• $1 \leq A_i \neq B_i \leq N$
• $0 \leq W_i \leq 10^9$

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$5$	$N, M \leq 100$
$2$	$8$	$N, M \leq 2000$
$3$	$7$	$M = N - 1$
$4$	$15$	$M = N$
$5$	$16$	$W_i = 1$
$6$	$22$	$0 \leq W_i \leq 10$
$7$	$27$	无附加限制