{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA network of \u003cb\u003em\u003c/b\u003e roads connects \u003cb\u003eN\u003c/b\u003e cities (numbered from 1 to \u003cb\u003eN\u003c/b\u003e). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road \u003cb\u003ei\u003c/b\u003e from city \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e to city \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e:\u003c/p\u003e\u003cul\u003e\u003cli\u003ein advance, in a city \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e (which may or may not be the same as \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e);\u003c/li\u003e\u003cli\u003eafter the travel, in the city \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe payment is \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e in the first case and \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e in the second case.\u003c/p\u003e\u003cp\u003eWrite a program to find a minimal-cost route from the city 1 to the city \u003cb\u003eN\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains the values of \u003cb\u003eN\u003c/b\u003e and \u003cb\u003em\u003c/b\u003e. Each of the following \u003cb\u003em\u003c/b\u003e lines describes one road by specifying the values of \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e (1 ≤ \u003cb\u003ei \u003c/b\u003e≤ \u003cb\u003em\u003c/b\u003e). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ \u003cb\u003em, N\u003c/b\u003e ≤ 10, 0 ≤ \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e , \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ 100, \u003cb\u003eP\u003c/b\u003e\u003csub\u003ei\u003c/sub\u003e ≤ \u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e (1 ≤ \u003cb\u003ei \u003c/b\u003e≤ \u003cb\u003em\u003c/b\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city \u003cb\u003eN\u003c/b\u003e. If the trip is not possible for any reason, the line must contain the word ‘\u003cb\u003eimpossible\u003c/b\u003e’.\u003c/p\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\u003e4 5\r\n1 2 1 10 10\r\n2 3 1 30 50\r\n3 4 3 80 80\r\n2 1 2 10 10\r\n1 3 2 10 50\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e110\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}