题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的点，以及 $M$ 条道路。第 $i$ 条（$1 \leq i \leq M$）道路双向连接点 $a_i$ 和点 $b_i$，通过需要 $c_i$ 分钟。可以使用一些道路从任意一个点到达任意其他点。点 $1$ 到点 $K$ 上有一些房子。

对于 $i=1,\ldots,Q$，解决以下问题。

Takahashi 当前位于点 $x_i$ 上的房子，并希望前往点 $y_i$ 上的房子。
自上次睡眠后经过了 $t_i$ 分钟后，他不能继续移动。
他只能在有房子的点休息，但可以多次休息。
如果他可以从点 $x_i$ 到达点 $y_i$，则输出 Yes；否则输出 No。

约束条件

• $2 \leq K \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq \min (2 \times 10^5, \frac{N(N-1)}{2})$
• $1 \leq a_i < b_i \leq N$
• 若 $i \neq j$，则 $(a_i,b_i) \neq (a_j,b_j)$。
• $1 \leq c_i \leq 10^9$
• 可以使用一些道路从任意一个点到达任意其他点。
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq x_i < y_i \leq K$
• $1 \leq t_1 \leq \ldots \leq t_Q \leq 10^{15}$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式获取输入数据：

$N$ $M$ $K$ $a_1$ $b_1$ $c_1$ $\vdots$ $a_M$ $b_M$ $c_M$ $Q$ $x_1$ $y_1$ $t_1$ $\vdots$ $x_Q$ $y_Q$ $t_Q$

输出

打印 $Q$ 行。第 $i$ 行应包含第 $i$ 个问题的答案。

示例输入 1

6 6 3
1 4 1
4 6 4
2 5 2
3 5 3
5 6 5
1 2 15
3
2 3 4
2 3 5
1 3 12

示例输出 1

No
Yes
Yes

在第 $3$ 个问题中，从点 $1$ 直接到达点 $3$ 至少需要 $13$ 分钟。然而，他可以首先在 $12$ 分钟内前往点 $2$，在那里休息，然后前往点 $3$。因此，答案是 Yes。