{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou and your friends are going to camping next weekend , because you are the best driver and you are living in this town for ten years , you have to drive the car from your home and pick up each of your friends to take them with you ,then finally go to the camping site. You have the map of the town and the length of every street ,and homes of friends will be at some intersections. you want to start from your home then pick up all of your friends then go to the camping site as fast as you can so you have to find the shortest path to do that. you can pick up your friends in any order but you have to make sure you pick up all of them. NOTE: you can pass by any intersection more than once including home and camping site . \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eYour program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e T \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 50). Followed by the test cases, the first line of each test case contains three integers N,M,F (3 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e N \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 100 , 0\u0026lt;M \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e (N*(N-1))/2 , 1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e F \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 9 ) representing the number of intersections , the number of streets and number of friends respectively. Followed by M lines, each line contains 3 integers separated by a single space X Y Z (1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e X, Y \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e N), (1 \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e Z \u003cspan class\u003d\"tex-span\"\u003e ≤ \u003c/span\u003e 1000) which represent a street between intersection X and intersection Y with length Z in both direction (X and Y will be different). then follow F (1\u0026lt;fr\u0026lt;N) deferent integer representing friends home number(number of intersection where home is located). your home is at intersection number one and camping site is at intersection number N. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print a single line containing \"Case n:\" (without quotes) where n is the test case number (starting from 1) followed by a space then the shortest path to go from your home to camping site after picking up all your friends . \u003c/p\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\u003e2\n4 4 2\n1 4 3\n1 2 2\n2 3 2\n3 4 2\n2 3\n6 8 2\n1 2 1\n2 3 2\n3 6 3\n1 4 11\n4 5 2\n5 6 20\n5 3 5\n4 3 10\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 6\nCase 2: 20\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\u003ein the second test case the shortest path is : 1 \u0026gt; 2 \u0026gt; 3 \u0026gt; 5 \u0026gt; 4 \u0026gt; 5 \u0026gt; 3 \u0026gt; 6\u003c/p\u003e"}}]}