{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn a country, there is a number of cities connected by unidirectional roads. Due to\r\ninsufficient budget, some roads are covered with pot-holes, so certain\r\ncars cannot use certain roads. Thus each road has the height number\r\nassociated with it\u0026nbsp;— that is the minimal height of the bottom of a car\r\nthat can drive through that road. On the other hand, some roads are private,\r\nand one should pay for using them. Luckily, the amount to be paid is\r\nstandartized and equals one standard unit. Finally, for each road, the time\r\nrequired to drive through it is known.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eGiven that you have to drive from city \u003ci\u003es\u003c/i\u003e to city \u003ci\u003ef\u003c/i\u003e using no more than\r\n\u003ci\u003et\u003c/i\u003e minutes of time, no more than \u003ci\u003eb\u003c/i\u003e standard units, find the\r\nminimal height of the bottom of the car which makes it possible.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line of the input contains the number of cities \u003ci\u003en\u003c/i\u003e (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003en\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;100), the number of roads \u003ci\u003em\u003c/i\u003e\r\n(1\u0026nbsp;≤\u0026nbsp;\u003ci\u003em\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10\u003csup\u003e4\u003c/sup\u003e), and the numbers of starting and ending cities \u003ci\u003es\u003c/i\u003e\r\nand \u003ci\u003ef\u003c/i\u003e (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003es\u003c/i\u003e, \u003ci\u003ef\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;\u003ci\u003en\u003c/i\u003e).\r\nThe second line contains numbers \u003ci\u003eb\u003c/i\u003e (0\u0026nbsp;≤\u0026nbsp;\u003ci\u003eb\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10\u003csup\u003e6\u003c/sup\u003e) and \u003ci\u003et\u003c/i\u003e\r\n(0\u0026nbsp;≤\u0026nbsp;\u003ci\u003et\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10\u003csup\u003e6\u003c/sup\u003e).\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEach of the next \u003ci\u003em\u003c/i\u003e lines has the form \u003ci\u003eu\u003csub\u003ei\u003c/sub\u003e v\u003csub\u003ei\u003c/sub\u003e c\u003csub\u003ei\u003c/sub\u003e t\u003csub\u003ei\u003c/sub\u003e h\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e.\r\nHere, \u003ci\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the starting city for \u003ci\u003ei\u003c/i\u003e-th road, \u003ci\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the ending city,\r\n\u003ci\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is 1 if it is a private road and 0 otherwise, \u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the time\r\nrequired to drive through that road, and \u003ci\u003eh\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the height of the car\r\nrequired to pass (1\u0026nbsp;≤\u0026nbsp;\u003ci\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;\u003ci\u003en\u003c/i\u003e; 0\u0026nbsp;≤\u0026nbsp;\u003ci\u003et\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10\u003csup\u003e4\u003c/sup\u003e; \r\n0\u0026nbsp;≤\u0026nbsp;\u003ci\u003eh\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10\u003csup\u003e6\u003c/sup\u003e). All the numbers in the input are integers.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf there is no way to drive from \u003ci\u003es\u003c/i\u003e to \u003ci\u003ef\u003c/i\u003e under given restrictions,\r\noutput \"−1\". Otherwise write on the first line the minimal height\r\nof the car; the second line should contain the number of roads used to travel\r\nfrom \u003ci\u003es\u003c/i\u003e to \u003ci\u003ef\u003c/i\u003e; and the third line must be filled by the numbers of the roads\r\nyou used in the order of usage. Roads are numbered from 1 to \u003ci\u003em\u003c/i\u003e; the\r\norder is the same as in input.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","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 2 1 2\r\n1 100\r\n1 2 1 100 77\r\n1 2 1 100 66\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e66\r\n1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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 2 1 2\r\n0 100\r\n1 2 0 101 77\r\n1 2 1 100 66\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}