Score : $575$ points

问题陈述

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

对于每个$i = 1, \ldots, M$，确定以下两个值是否不同。

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

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

以上为大语言模型 kimi 翻译，仅供参考。

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$.