题目描述

$1$ から $N$ までの番号がついた $N$ 個の地点と $M$ 本の道があります。 $i\ \,\ (1\ \leq\ i\ \leq\ 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$ $\vdots$ $a_M$ $b_M$ $c_M$ $Q$ $x_1$ $y_1$ $t_1$ $\vdots$ $x_Q$ $y_Q$ $t_Q$

输出格式

$Q$ 行出力せよ。 $i$ 行目には、$i$ 番目の問題に対する出力をせよ。

题目大意

给定一张 $n$ 个点 $m$ 条边的无向连通简单图。每条边存在 $a_i, b_i, c_i$，表示 $a_i \rightarrow b_i$ 或 $b_i \rightarrow a_i$ 耗时 $c_i$。给定 $k$，定义 $n$ 个点中只有前 $k$ 个点有房子，$q$ 次询问，每次给定 $x, y, t$，求从 $x$ 到 $y$ 连续的不在房子中的时间是否一定会超过 $t$，超过输出 No，反之输出 Yes。保证询问中 $t$ 满足升序。

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

提示

制約

• $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} $
• 入力は全て整数

Sample Explanation 1

$3$ 番目の問題において、地点 $1$ から地点 $3$ に直接向かうと $13$ 分以上かかります。しかし、 $12$ 分かけて地点 $2$ に移動し、そこにある家で睡眠を取ってから地点 $3$ に移動することが出来ます。よって、答えは Yes となります。