{"problem":{"name":"Ex - Trespassing Takahashi","description":{"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 ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc250_h"},"statements":[{"statement_type":"Markdown","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`.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc250_h","tags":[],"sample_group":[["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","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`."]],"created_at":"2026-03-03 11:01:14"}}