{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/d3352bafb620ca47927d95ba278fb1d7?v\u003d1715734034\" alt\u003d\"/problems/slowleak/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eYou are an avid cyclist and bike every day between your home\n and school. Usually, your ride is uneventful and you bike along\n the shortest path between home and school. After school this\n afternoon you realized you have a slow leak in your bike\n tire—the tire can hold some air, but not for long. Refilling\n the tire allows you to ride your bike for some distance, after\n which your tire goes flat again and it becomes impossible to\n ride any further (and you refuse to walk your bicycle).\u003c/p\u003e\n \u003cp\u003eLuckily for you, your city has installed several bike repair\n stations at intersections throughout town where you can refill\n your tire and bike again until the tire goes flat. There’s a\n repair station at your school too, so that you can fill up your\n tire before you start on your trip home.\u003c/p\u003e\n \u003cp\u003eYou’ve calculated how far you can bike before your tire runs\n out of air and you know the layout of your town, including all\n the intersections, distances between them, and the locations of\n the repair stations. What is the shortest possible trip from\n school to your home that you can take without becoming stuck\n due to a flat tire? (You do not become stuck if you roll into a\n repair station, or your home, at the exact same time as your\n tire goes flat.)\u003c/p\u003e\n \u003cdiv id\u003d\"fig:slowleak\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/11ee430f3760b0f2f741e491429a74fa?v\u003d1715734034\" alt\u003d\"\\includegraphics[width\u003d0.7\\textwidth ]{samples.pdf}\" style\u003d\"width:70.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: An illustration of the two sample\n inputs.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains four integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e, satisfying \u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\le n \\le 500$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; m \\le n(n-1)/2$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; t \u0026lt; n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; d \u0026lt; 2^{31}$\u003c/span\u003e. The value\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e represents the number\n of intersections in the city, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e represents the number of roads in\n the city, \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e is the\n number of repair stations and \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e is the distance that you can bike\n (starting with a fully inflated tire) before your tire goes\n flat again. The intersections are numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. Your school is at intersection\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and your home is at\n intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eThe second line of input contains \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e integers, with values between\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e, inclusive. These are the\n intersections where the repair stations are located (excluding\n your school’s repair station). All integers on this line are\n unique.\u003c/p\u003e\n \u003cp\u003eThe next \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines\n represent the roads in your town. Each has three integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i, j, k$\u003c/span\u003e, where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le i \u0026lt; j \\le n$\u003c/span\u003e,\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; k \u0026lt;\n 2^{31}$\u003c/span\u003e. These three integers represent that there is a\n direct road from intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e to intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e of length \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e. Roads can be traveled in either\n direction. There is at most one road between any two\n intersections.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003ePrint the minimum total distance you need to travel to reach\n home from school without getting stuck due to a flat tire. If\n the trip is not possible, output the word \u003ctt class\u003d\"ttfamily\"\u003estuck\u003c/tt\u003e on a single line instead.\u003c/p\u003e\n \u003cp\u003eIt is guaranteed that if the trip is possible, the minimum\n distance \u003cspan class\u003d\"tex2jax_process\"\u003e$D$\u003c/span\u003e satisfies\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \u0026lt; D \u0026lt;\n 2^{31}$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample Explanation\u003c/h2\u003e\n \u003cp\u003eIn the first sample input, if your tire did not have a leak\n then the shortest path home would have a distance of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e, going from the school\n through intersections \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e. However, due to\n the leak, you can only travel a distance of \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e before you need to refill the\n tire, requiring you to use the repair stations at intersections\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e, for a total distance of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$12$\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eIn the second sample input, if your tire did not have a\n leak, then the shortest path home would have a distance of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$12$\u003c/span\u003e. But since your tire\n only lasts for a distance of \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e, there’s no path where your bike\n tire will not go flat somewhere along the way. Even when using\n repair station at intersection \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e, you get stuck before you can\n reach either your home or the repair station at intersection\n \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e6 7 2 4\n2 5\n1 2 4\n1 3 5\n2 3 3\n3 4 2\n3 5 1\n4 6 4\n5 6 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e6 7 2 10\n2 5\n1 2 1\n1 3 2\n2 3 1\n3 4 8\n4 5 3\n4 6 2\n5 6 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003estuck\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}