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 翻译