AT_past202203_k.旅行計画

给定一个有 $N$ 个顶点、$M$ 条边的带权有向图。

顶点编号为 $1$ 到 $N$。
第 $i$ 条边（$1 \leq i \leq M$）从顶点 $u_i$ 指向顶点 $v_i$，其权重为 $w_i$。

对于 $k=1,2,\ldots,N$，请解决以下问题：

• 判断是否存在一条从顶点 $1$ 出发，至少经过一次顶点 $k$，最终到达顶点 $N$ 的路径；如果存在，请输出这些路径中最短的长度。

输入以如下格式从标准输入给出。

$N$ $M$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\hspace{0.8cm}\vdots$
$u_M$ $v_M$ $w_M$

请输出 $N$ 行。对于第 $i$ 行（$1 \leq i \leq N$），输出 $k=i$ 时的答案：

• 如果存在一条从顶点 $1$ 出发，至少经过一次顶点 $k$，最终到达顶点 $N$ 的路径，则输出这些路径中最短的长度。
• 如果不存在这样的路径，则输出 -1。

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $1 \leq w_i \leq 10^9$
• 输入均为整数

样例解释 1

• 当 $k=1$ 时，直接通过第 $3$ 条边到达顶点 $3$ 的路径最短。
• 当 $k=2$ 时，先通过第 $1$ 条边到达顶点 $2$，再通过第 $2$ 条边到达顶点 $3$ 的路径最短。
• 当 $k=3$ 时，直接通过第 $3$ 条边到达顶点 $3$ 的路径最短。

由 ChatGPT 4.1 翻译