103756: [Atcoder]ABC375 G - Road Blocked 2

Problem Statement

In the nation of AtCoder, there are $N$ cities numbered $1$ to $N$, and $M$ roads numbered $1$ to $M$.
Road $i$ connects cities $A_i$ and $B_i$ bidirectionally and has a length of $C_i$.

For each $i = 1, \ldots, M$, determine whether the following two values are different.

• The shortest distance from city $1$ to city $N$ when all roads are passable
• The shortest distance from city $1$ to city $N$ when the $M - 1$ roads other than road $i$ are passable

If city $N$ can be reached from city $1$ in one of these cases but not the other, the two values are considered different.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N$
• All pairs $(A_i, B_i)$ are distinct.
• $1 \leq C_i \leq 10^9$
• City $N$ can be reached from city $1$ when all roads are passable.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

Output

Print $M$ lines. The $i$-th line should contain Yes if the shortest distance from city $1$ to city $N$ when all roads are passable is different from the shortest distance when the $M - 1$ roads other than road $i$ are passable, and No otherwise.

If city $N$ can be reached from city $1$ in one of these cases but not the other, the two values are considered different.

Sample Input 1

3 3
1 2 5
1 3 10
2 3 6

Sample Output 1

No
Yes
No

When all roads are passable, the shortest distance from city $1$ to city $3$ is $10$.

• When the two roads other than road $1$ are passable, the shortest distance is $10$.
• When the two roads other than road $2$ are passable, the shortest distance is $11$.
• When the two roads other than road $3$ are passable, the shortest distance is $10$.

Sample Input 2

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

Sample Output 2

No
No
No
No
No
Yes

When all roads are passable, the shortest distance from city $1$ to city $4$ is $1$.

When the five roads other than road $6$ are passable, the shortest distance is $2$.

Sample Input 3

2 1
1 2 1

Sample Output 3

Yes

When the zero roads other than road $1$ are passable, city $2$ cannot be reached from city $1$.

问题陈述

在AtCoder国，有N个城市，编号为1到N，和M条道路，编号为1到M。
道路i双向连接城市A_i和B_i，长度为C_i。

对于每个i = 1, …, M，判断以下两个值是否不同。

• 当所有道路都可通过时，从城市1到城市N的最短距离
• 除了道路i之外的其他M - 1条道路都可通过时，从城市1到城市N的最短距离

如果在这两种情况下，城市N可以从城市1到达，但另一种情况不可以，则这两个值被认为是不同的。

约束条件

• 2 ≤ N ≤ 2 × 10^5
• 1 ≤ M ≤ 2 × 10^5
• 1 ≤ A_i < B_i ≤ N
• 所有(A_i, B_i)对都是不同的。
• 1 ≤ C_i ≤ 10^9
• 当所有道路都可通过时，城市N可以从城市1到达。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

N M
A_1 B_1 C_1
…
A_M B_M C_M

输出

打印M行。第i行应包含Yes，如果当所有道路都可通过时，从城市1到城市N的最短距离与当除了道路i之外的M - 1条道路都可通过时的最短距离不同；否则打印No。

如果在这两种情况下，城市N可以从城市1到达，但另一种情况不可以，则这两个值被认为是不同的。

示例输入1

3 3
1 2 5
1 3 10
2 3 6

示例输出1

No
Yes
No

当所有道路都可通过时，从城市1到城市3的最短距离是10。

• 当除了道路1之外的两条道路都可通过时，最短距离是10。
• 当除了道路2之外的两条道路都可通过时，最短距离是11。
• 当除了道路3之外的两条道路都可通过时，最短距离是10。

示例输入2

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

示例输出2

No
No
No
No
No
Yes

当所有道路都可通过时，从城市1到城市4的最短距离是1。

当除了道路6之外的五条道路都可通过时，最短距离是2。

示例输入3

2 1
1 2 1

示例输出3

Yes

当除了道路1之外没有道路可通过时，城市2不能从城市1到达。