{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e一个道路网连接了N个城市(从1个城市到N个城市),可能有一条以上的道路连接一个城市和另一个城市。有些道路是有偿的。从城市Ai到城市Bi,有两种方式支付旅行费用:\n在城市Ci提前支付pi(Ci可能不等于Ai);\n出差后在城市Bi支付。它花费了Ri。\u003c/p\u003e\n \u003cp\u003e编写一个程序,从城市1到城市N找到一个最低成本的路线。\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e输入的第一行包含N和m的值,下面的m行通过指定ai、bi、ci、Pi、Ri的值来描述一条路。同一行的相邻值由一个或多个空格分隔。所有值是整数,1≤m,N≤10 0≤R P≤≤100。\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e文件中唯一的一行必须包含从城市1到城市的最小可能的花费。如果因为任何原因,旅行是不可能的,你应该把“不可能”这个词写出来。\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4 5\n1 2 1 10 10\n2 3 1 30 50\n3 4 3 80 80\n2 1 2 10 10\n1 3 2 10 50\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e110\u003c/pre\u003e"}}]}