{"trustable":false,"sections":[{"title":"Statement","value":{"format":"HTML","content":"Jonas is renowned for his ability for always selecting the shortest path. Journalist Masud is looking for details regarding the most recent Jonas trip. He was able to gather proof that Jonas visited several cities during this tour. Although the entire journey is (one of) the shortest path between these locations, there is no information regarding the sequence in which they were visited or the starting or ending cities of his journey. Find the shortest path that contains all specified cities.\u003cbr\u003eCountry in which Jonas traveled consists of \u003ci\u003en\u003c/i\u003e cities and \u003ci\u003em\u003c/i\u003e undirected roads between them. For each road Masud knows the time it takes to travel it, and the \"shortest\" word above is with respect to those times.\u003cbr\u003eIt is guaranteed that there exists some shortest path going through all specified cities.\u003cbr\u003e\n "}},{"title":"Input","value":{"format":"HTML","content":"First line contains two integers \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e. Each of the \u003ci\u003em\u003c/i\u003e following lines contains a description of a single road \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e which means Jonas can go between \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e and \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e by road and that will take \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e seconds. The next line contains \u003ci\u003ek\u003c/i\u003e\u0026nbsp;— the number of cities that Masud knows Jonas has visited. The last line contains a list of these cities. All cities in that list are distinct.\u003cbr\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e , \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup\u003e4\u003c/sup\u003e\u003c/li\u003e\n \u003cli\u003e\u003ci\u003ea\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/li\u003e\n\u003cul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"The number of roads in the desired shortest path should be printed on the first line. On the second line output the list of road numbers (numbered in the order of appearing in the input) in the order of that shortest path. Output any if there are several options.\u003cbr\u003e"}},{"title":"Sample 1","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\u003e6 6\n1 2 2\n2 6 2\n1 3 1\n3 4 1\n4 5 1\n5 6 1\n3\n5 1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","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\u003e6 6\n1 2 2\n2 6 2\n1 3 1\n3 4 1\n4 5 1\n5 6 1\n2\n1 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}