{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e一个包含\u003cb\u003em\u003c/b\u003e条道路连接了\u003cb\u003eN\u003c/b\u003e个城市(编号从1到\u003cb\u003eN\u003c/b\u003e)。一个城市和另一个城市之间可能有多条道路相连。其中一些道路是收费的。有两种方式可以支付从城市\u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e到城市\u003cb\u003eb\u003csub\u003ei\u003c/b\u003e的收费道路\u003cb\u003ei\u003c/b\u003e:\u003c/p\u003e\u003cul\u003e\u003cli\u003e提前在城市\u003cb\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e支付(可能与\u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e相同);\u003c/li\u003e\u003cli\u003e在旅行后,在城市\u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e支付。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e第一种情况下支付\u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e,第二种情况下支付\u003cb\u003eR\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e。\u003c/p\u003e\u003cp\u003e编写一个程序,找到从城市1到城市\u003cb\u003eN\u003c/b\u003e的最小成本路线。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含\u003cb\u003eN\u003c/b\u003e和\u003cb\u003em\u003c/b\u003e的值。接下来的\u003cb\u003em\u003c/b\u003e行中,每行描述一条道路,指定了\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)。同一行上相邻的值之间用一个或多个空格分隔。所有值都是整数,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\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)。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e文件的第一行必须包含从城市1到城市\u003cb\u003eN\u003c/b\u003e的最小可能成本。如果由于任何原因旅行不可能,该行必须包含单词“\u003cb\u003eimpossible\u003c/b\u003e”。\u003c/p\u003e"}},{"title":"样例","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"}}]}