{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"N个以数字1 ... N命名的城市通过单向道路相连。每条道路都有两个相关参数:道路长度和需要支付的通行费(以硬币数量表示)。\n\u003cbr\u003e鲍勃和爱丽丝曾经住在城市1。在注意到爱丽丝在他们喜欢玩的纸牌游戏中作弊后,鲍勃和她分手并决定搬到城市N。他希望尽快到达那里,但他手头缺钱。\n\u003cbr\u003e\n\u003cbr\u003e我们希望帮助鲍勃找到从城市1到城市N的\u003cb\u003e最短路径\u003c/b\u003e,\u003cb\u003e他能够负担得起\u003c/b\u003e的路径,即用他手头的钱支付得起的路径。\n\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含整数K,0 ≤ K ≤ 10000,鲍勃在路上可以花费的最大硬币数量。\n\u003cbr\u003e第二行包含整数N,2 ≤ N ≤ 100,城市的总数。\n\u003cbr\u003e\n\u003cbr\u003e第三行包含整数R,1 ≤ R ≤ 10000,道路的总数。\n\u003cbr\u003e\n\u003cbr\u003e接下来的R行中,每行描述一条道路,通过用单个空格分隔的整数S、D、L和T来指定: \n\u003cbr\u003e\u003cul\u003e\u003cli\u003eS是起始城市,1 ≤ S ≤ N \n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eD是目的地城市,1 ≤ D ≤ N \n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eL是道路长度,1 ≤ L ≤ 100 \n\u003cbr\u003e\u003c/li\u003e\u003cli\u003eT是通行费(以硬币数量表示),0 ≤ T ≤100\u003c/li\u003e\u003c/ul\u003e\n\u003cbr\u003e请注意,不同的道路可能具有相同的起始和目的地城市。"}},{"title":"输出","value":{"format":"HTML","content":"输出的第一行应包含从城市1到城市N的最短路径的总长度,其总通行费小于或等于K个硬币。\n\u003cbr\u003e如果不存在这样的路径,则输出应只写入数字-1。\n\u003cbr\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\u003e5\r\n6\r\n7\r\n1 2 2 3\r\n2 4 3 3\r\n3 4 2 4\r\n1 3 4 1\r\n4 6 2 1\r\n3 5 2 0\r\n5 4 3 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}