擅自闯入的高桥君

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的点，以及 $M$ 条道路。第 $i$ 条（$1 \le i \le M$）道路双向连接点 $a_i$ 和点 $b_i$，通过需要 $c_i$ 分钟。可以从任意一个点经过若干条道路到达任意另一个点。在点 $1,\ldots,K$ 上有房子。

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

高桥君目前在点 $x_i$ 的房子处，想要前往点 $y_i$ 的房子处。

自从上次睡觉以来过了 $t_i$ 分钟后，他就不能再继续移动了。

他只能在有房子的点睡觉，但可以睡任意多次。

如果他能从点 $x_i$ 旅行到点 $y_i$，打印 Yes；否则打印 No。

输入格式

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

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

输出格式

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

样例

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

No
Yes
Yes

在第 3 个问题中，从点 $1$ 直接到达点 $3$ 至少需要 $13$ 分钟。但是，他可以先用 $12$ 分钟到达点 $2$，在房子那里睡觉，然后再前往点 $3$。因此答案是 Yes。

数据范围

• $2 \le K \le N \le 2 \times 10^5$
• $N-1 \le M \le \min (2 \times 10^5, \frac{N(N-1)}{2})$
• $1 \le a_i \lt b_i \le N$
• 若 $i \neq j$，则 $(a_i,b_i) \neq (a_j,b_j)$
• $1 \le c_i \le 10^9$
• 可以从任意一个点经过若干条道路到达任意另一个点
• $1 \le Q \le 2 \times 10^5$
• $1 \le x_i \lt y_i \le K$
• $1 \le t_1 \le \ldots \le t_Q \le 10^{15}$
• 输入中的所有值均为整数。