{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" Andrew has just made a breakthrough in urban orienteering: he realized that each urban orienteering contest, like the upcoming \"Running City Petrozavodsk\", can be represented as a simple problem in graph theory. Your task is to get from point \u003ci\u003eA\u003c/i\u003e to point \u003ci\u003eB\u003c/i\u003e in the city as fast as you can. City map consists of roads (corresponding to edges of a graph) and road intersections (corresponding to nodes of a graph). Points \u003ci\u003eA\u003c/i\u003e and \u003ci\u003eB\u003c/i\u003e are road intersections, of course. You know the running times for all roads in the city. However, you won\u0027t be able to solve your problem with a usual Dijkstra algorithm, because there are some additional difficulties. There are some \u003ci\u003eroutes\u003c/i\u003e in the city which slow you down. Some friends in the organizing committee gave you the secret map where those routes are marked. A route can be any simple path (no intersection can appear twice) in the graph. The difficulty is: if you run through the whole route, a group of volunteers waits for you in the end of the route, and the celebration begins\u003cimg src\u003d\"CDN_BASE_URL/773046a643c41d32918200584b0acd98?v\u003d1719362561\" style\u003d\"vertical-align: text-bottom;top: -2.0px;max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;It slows you down by the time equal to the time you spent running through the route. So it\u0027s like if you ran through the route 2 times. Also, if your path contains several such routes as subpaths, then each of them counts. For example, there can be two exactly equal routes in the input, and if your path contains such route, then it\u0027s actually as if you ran 3 times through the route. Find the shortest time to get from one node to another in such a strange graph with \"bonuses\". \u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003eFirst line of the input file contains five integers \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e, \u003ci\u003eS\u003c/i\u003e, \u003ci\u003eT\u003c/i\u003e — number of nodes, edges, special routes in the graph, start node and finish node respectively. \u003cimg src\u003d\"CDN_BASE_URL/b6f12393ee142a2b09059d1a834e7e74?v\u003d1719362561\" style\u003d\"vertical-align: text-bottom;top: -2.0px;max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg src\u003d\"CDN_BASE_URL/b04368e919aa253d2b520312ccbeabab?v\u003d1719362561\" style\u003d\"vertical-align: text-bottom;top: -2.0px;max-width: 100.0%;max-height: 100.0%;\"\u003e, \u003cimg src\u003d\"CDN_BASE_URL/5f3d11771dc730e7718a0f20297295ff?v\u003d1719362561\" style\u003d\"vertical-align: text-bottom;top: -2.0px;max-width: 100.0%;max-height: 100.0%;\"\u003e, 1 ≤ \u003ci\u003eS\u003c/i\u003e, \u003ci\u003eT\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003eS\u003c/i\u003e ≠ \u003ci\u003eT\u003c/i\u003e. The nodes in the graph are numbered from 1 to \u003ci\u003en\u003c/i\u003e. Each of the following \u003ci\u003em\u003c/i\u003e lines contains three integers \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e, \u003ci\u003ec\u003c/i\u003e, (\u003cimg src\u003d\"CDN_BASE_URL/69867b08233d5023afe50bb482799dcb?v\u003d1719362561\" style\u003d\"vertical-align: text-bottom;top: -2.0px;max-width: 100.0%;max-height: 100.0%;\"\u003e), where \u003ci\u003ea\u003c/i\u003e and \u003ci\u003eb\u003c/i\u003e are nodes and \u003ci\u003ec\u003c/i\u003e is the time to run through the edge (\u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e). The graph is directed: you can\u0027t run from \u003ci\u003eb\u003c/i\u003e to \u003ci\u003ea\u003c/i\u003e along the edge (\u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e). There are no more than 10 edges going out from each node. Each of the next \u003ci\u003er\u003c/i\u003e lines contains a description of a special route. It begins with integer \u003ci\u003ek\u003c/i\u003e — the number of edges in the route. Then \u003ci\u003ek\u003c/i\u003e integers follow — the numbers of the edges in the route. Edges are numbered from 1 to \u003ci\u003em\u003c/i\u003e in the same order that they are written above. Sum of lengths of all routes is not more than 2m. Each edge occurs no more than in 10 special routes. Each special route is correct: no vertex can appear twice in any given route, and the end of each edge of the route except the last one coincides with the start of the next edge. \u003cbr\u003e\u003cdiv align\u003d\"left\" style\u003d\"margin-top: 1.0em;\"\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003eIf there is a way from \u003ci\u003eS\u003c/i\u003e to \u003ci\u003eT\u003c/i\u003e, print the minimal time to get from \u003ci\u003eS\u003c/i\u003e to \u003ci\u003eT\u003c/i\u003e and any optimal path, otherwise just print -1. The format of output in case a way exists: on the first line print the minimal time, on the second line print the number of edges in the path and on the last line print the sequence of numbers of edges (ranging from 1 to \u003ci\u003em\u003c/i\u003e) that form the optimal path. \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\u003e3 3 1 1 3\n1 2 2\n2 3 1\n1 3 2\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n1 2 \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\u003e3 3 3 1 3\n1 2 2\n2 3 2\n1 3 1\n1 3\n1 3\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2\n1 2 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","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 3 1 4\n1 2 3\n2 3 2\n3 4 1\n3 1 2 3\n2 2 3\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\n3\n1 2 3 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}