Ex - 闯入高桥家

得分：$600$ 分

问题描述

有 $N$ 个编号从 $1$ 到 $N$ 的点和 $M$ 条道路。第 $i$ 条 ($1 \leq i \leq M$) 道路双向连接着点 $a_i$ 和点 $b_i$ ，通过道路需要 $c_i$ 分钟。任意两个点之间可以通过一些道路来进行旅行。1号到$K$号点上有房子。

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

高桥从位于点 $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 \lt 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 \lt 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。