{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory\u0027s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory\u0027s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.\u003cbr\u003eCountry in which Gregory traveled consists of \u003ci\u003en\u003c/i\u003e cities and \u003ci\u003em\u003c/i\u003e undirected roads between them. For each road Ostap 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\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eFirst line contains two integers \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e (1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\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 (\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, 1 ≤ \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, 1 ≤ \u003ci\u003et\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup\u003e4\u003c/sup\u003e) means Gregory 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 Ostap knows Gregory has visited. The last line contains a list of these cities. All cities in that list are distinct.\u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eOn the first line output the number of roads in the sought shortest path. 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. If there are many solutions, output any.\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"}}]}