AT_abc375_g [ABC375G] Road Blocked 2

在 AtCoder 国有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条道路，编号为 $1$ 到 $M$。 第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，是双向的，长度为 $C_i$。 对于每个 $i=1,\ldots,M$，请判断以下两个值是否不同： - 当所有道路都可通行时，从城市 $1$ 到城市 $N$ 的最短距离； - 当除了第 $i$ 条道路以外的其余 $M-1$ 条道路可通行时，从城市 $1$ 到城市 $N$ 的最短距离。 注意，如果一种情况下可以从城市 $1$ 到城市 $N$，而另一种情况下无法到达，则认为这两个值是不同的。

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

输出 $M$ 行。第 $i$ 行输出如下内容： - 如果“所有道路都可通行时，从城市 $1$ 到城市 $N$ 的最短距离”与“除了第 $i$ 条道路以外的其余 $M-1$ 条道路可通行时，从城市 $1$ 到城市 $N$ 的最短距离”不同，则输出 `Yes`； - 如果相同，则输出 `No`。 注意，如果一种情况下可以从城市 $1$ 到城市 $N$，而另一种情况下无法到达，则认为这两个值是不同的。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $1 \leq A_i < B_i \leq N$ - $(A_i,B_i)$ 互不相同 - $1 \leq C_i \leq 10^9$ - 当所有道路都可通行时，一定可以从城市 $1$ 到城市 $N$ - 所有输入均为整数 ### 样例解释 1 当所有道路都可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $10$。 - 当除了第 $1$ 条道路以外的其余 $2$ 条道路可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $10$。 - 当除了第 $2$ 条道路以外的其余 $2$ 条道路可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $11$。 - 当除了第 $3$ 条道路以外的其余 $2$ 条道路可通行时，从城市 $1$ 到城市 $3$ 的最短距离为 $10$。 ### 样例解释 2 当所有道路都可通行时，从城市 $1$ 到城市 $4$ 的最短距离为 $1$。 当除了第 $6$ 条道路以外的其余 $5$ 条道路可通行时，从城市 $1$ 到城市 $4$ 的最短距离为 $2$。 ### 样例解释 3 当除了第 $1$ 条道路以外的 $0$ 条道路可通行时，无法从城市 $1$ 到城市 $2$。 由 ChatGPT 4.1 翻译