道路封锁 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$ 条道路可通行时的最短距离不同,则输出 Yes,否则输出 No。

若在一种情况下可以从城市 $1$ 到达城市 $N$,而另一种情况下不能,则认为这两个值不同。

样例

3 3
1 2 5
1 3 10
2 3 6

No
Yes
No

所有道路均可通行时,从城市 $1$ 到城市 $3$ 的最短距离为 $10$。

当除道路 $1$ 外的两条道路可通行时,最短距离为 $10$。

当除道路 $2$ 外的两条道路可通行时,最短距离为 $11$。

当除道路 $3$ 外的两条道路可通行时,最短距离为 $10$。

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

No
No
No
No
No
Yes

所有道路均可通行时,从城市 $1$ 到城市 $4$ 的最短距离为 $1$。

当除道路 $6$ 外的五条道路可通行时,最短距离为 $2$。

2 1
1 2 1

Yes

当除道路 $1$ 外零条道路可通行时,从城市 $1$ 无法到达城市 $2$。

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_i \lt B_i \le N$
• 所有 $(A_i, B_i)$ 两两不同。
• $1 \le C_i \le 10^9$
• 在所有道路均可通行时,可以从城市 $1$ 到达城市 $N$。
• 所有输入值均为整数。