{"raw_statement":[{"iden":"problem statement","content":"There are $N$ points numbered $1$ through $N$, and $M$ roads. The $i$\\-th ($1 \\leq i \\leq M$) road connects Point $a_i$ and Point $b_i$ bidirectionally and requires $c_i$ minutes to pass through. One can travel from any point to any other point using some number of roads. There is a house on Points $1,\\ldots, K$.\nFor $i=1,\\ldots,Q$, solve the following problem.\n\n> Takahashi is currently at the house at Point $x_i$ and wants to travel to the house at Point $y_i$.  \n> Once $t_i$ minutes have passed since his last sleep, he cannot continue moving anymore.  \n> He can get sleep only at a point with a house, but he may do so any number of times.  \n> If he can travel from Point $x_i$ to Point $y_i$, print `Yes`; otherwise, print `No`."},{"iden":"constraints","content":"*   $2 \\leq K \\leq N \\leq 2 \\times 10^5$\n*   $N-1 \\leq M \\leq \\min (2 \\times 10^5, \\frac{N(N-1)}{2})$\n*   $1 \\leq a_i \\lt b_i \\leq N$\n*   If $i \\neq j$, then $(a_i,b_i) \\neq (a_j,b_j)$.\n*   $1 \\leq c_i \\leq 10^9$\n*   One can travel from any point to any other point using some number of roads.\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $1 \\leq x_i \\lt y_i \\leq K$\n*   $1 \\leq t_1 \\leq \\ldots \\leq t_Q \\leq 10^{15}$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$\n$a_1$ $b_1$ $c_1$\n$\\vdots$\n$a_M$ $b_M$ $c_M$\n$Q$\n$x_1$ $y_1$ $t_1$\n$\\vdots$\n$x_Q$ $y_Q$ $t_Q$"},{"iden":"sample input 1","content":"6 6 3\n1 4 1\n4 6 4\n2 5 2\n3 5 3\n5 6 5\n1 2 15\n3\n2 3 4\n2 3 5\n1 3 12"},{"iden":"sample output 1","content":"No\nYes\nYes\n\nIn the $3$\\-rd problem, it takes no less than $13$ minutes from Point $1$ to reach Point $3$ directly. However, he can first travel to Point $2$ in $12$ minutes, get sleep in the house there, and then travel to Point $3$. Thus, the answer is `Yes`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}