AT_pakencamp_2023_day1_h Winter Road

在「パ研王国」有 $N$ 个村庄和 $M$ 条道路。第 $i$ 条道路连接了村庄 $A_i$ 和 $B_i$，且为双向道路，无论何种情况下通过任意一条道路都需要 $1$ 分钟。 最初，所有道路都覆盖着冰。如果 $C_i = -1$，则第 $i$ 条道路上的冰永远不会融化；如果 $1 \le C_i$，则在 $C_i$ 分钟后该道路上的冰会融化。 身为国王的「パケン君」初始位于村庄 $1$，他希望通过若干条道路移动到村庄 $N$。他可以在任意村庄等待，且由于小心谨慎，他希望尽量少地通过还结着冰的道路。请你计算：当他以最小化通过结冰道路的时间为目标从村庄 $1$ 移动到村庄 $N$ 时，总共所需的最短时间是多少。 保证存在至少一条路径使得从村庄 $1$ 到村庄 $N$ 可以通过若干道路到达。

输入以如下格式从标准输入给出。 > $N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

请输出以分钟为单位的最小总花费时间。

### 样例解释 1 如果直接从村庄 $1$ 走到村庄 $3$，则所需时间为 $1$ 分钟，但一定要经过一条结着冰的道路。然而，如果先到村庄 $2$，则可以避开结冰的道路再前往村庄 $3$。这种情况下，「パケン君」需要在村庄 $1$ 等待 $3$ 分钟。 ### 数据范围与约定 - $2 \leq N \leq 2\times 10^5$ - $N-1 \leq M \leq \min \left(\dfrac{N(N-1)}{2},\; 2\times 10^5\right)$ - $1 \le A_i < B_i \le N$ - 对于 $1 \le i < j \le N$，$(A_i,B_i) \neq (A_j,B_j)$ - $C_i = -1$ 或 $1 \le C_i \le 10^9$ - 所有输入均为整数 - 保证存在从村庄 $1$ 到村庄 $N$ 的路径。 由 ChatGPT 5 翻译