{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA thief is trying to escape the holds of the police through a city. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e nodes and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e edges.\u003c/p\u003e\u003cp\u003eThief is currently at vertex numbered \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e and needs to reach vertex numbered \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e. Thief moves with constant speed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eV\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/sub\u003e \u003d 1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e policemen are initially located in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e distinct locations denoted by \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Each policeman has a constant speed of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eV\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eP\u003c/i\u003e\u003c/sub\u003e \u003d 1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTo help policemen, a single power booster have been provided to them. This power booster can be availed once from any one of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e distinct ‘special’ nodes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Property of this power booster being that it doubles the speed of the policeman who avails this power booster.\u003c/p\u003e\u003cp\u003eNote: A policeman can choose not to avail the power booster even if he is at a ‘special’ node.\u003c/p\u003e\u003cp\u003eYou have to print the shortest time in which thief can escape the police regardless of whatever path the police might take. If he can’t reach the destination, output \u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e, the number of nodes and number of edges respectively.\u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines contain integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e denoting an undirected edge between nodes numbered \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e, \u003ci\u003ew\u003c/i\u003e\u003c/span\u003e being the weight of the edge. Next line contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e denoting number of different policemen. Next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e space separated integers denoting the distinct locations \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eNext line contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e denoting number of ‘special’ nodes. Next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e distinct space separated integers denoting the locations \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eNext line contains two distinct integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e denoting the source and destination of the thief.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print the minimum time required for thief to escape(if possible). Else, output \u003cspan class\u003d\"tex-span\"\u003e - 1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eConstraints\u003c/span\u003e \u003c/p\u003e\u003cul\u003e \u003cli\u003e 1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emin\u003c/i\u003e(2 * 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e, \u003ci\u003eN\u003c/i\u003e * (\u003ci\u003eN\u003c/i\u003e - 1) / 2)\u003c/span\u003e \u003c/li\u003e\u003cli\u003e 0 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e, \u003ci\u003eS\u003c/i\u003e, \u003ci\u003eD\u003c/i\u003e, \u003ci\u003eA\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eB\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eN\u003c/i\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e 0 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eY\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e 1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eX\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e 0 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eK\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eQ\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e 1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\n0 1 2\n1 2 4\n2 3 10\n3 0 2\n1\n3\n1\n0\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\n0 1 2\n1 2 8\n1 3 10\n2\n2 3\n2\n2 3\n0 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eExample1:\u003c/p\u003e\u003cp\u003ePolice takes the path \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e availing the power booster at node 0. Even though both policeman and thief reach the destination at same time, police catches thief.\u003c/p\u003e\u003cp\u003eExample2:\u003c/p\u003e\u003cp\u003eWhichever policeman uses the power booster, thief will be able to escape in \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e seconds.\u003c/p\u003e"}}]}