5 人解决，22 人已尝试。
11 份提交通过，共有 133 份提交。
8.8 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
McFn 和女朋友 Bonbon 吵架了，他现在心情很不好。所以他开着自己的小 QQ，打算到他好朋友 Toksky 和 Haozi 所在的城市散心。他想见他的朋友，越快越好。他现在有一张地图 , 地图上有 N 个城市，用 1…N 的数字标号。地图上有 M 条道路，每条道路连接两个城市，而却都是单向的，与此同时，每条道路都有一个收费站，你要经过它就必须交一定金额的过路费。但是小 A 身上的钱有限，McFn 数学很强，但是他现在脑子很乱，想让你帮忙解决这个问题 : 在他资金能够承受的范围内，帮他寻找一条从城市 1 到城市 N 的一条最短路径。
第一行有一个整数 T （1<=T<=20)，表示测试数据总数
每组 case 的第一行是一个整数 K, 表示 McFn 身上的钱的总数。(0<=K<=10000)
第二行是一个整数 N(1<=N<=100) 表示城市总数
第三行是一个整数 M(1<=M<=10000) 表示道路的总数
接下来的 M 行，每行有四个用空格间开的整数 S,D,L,C
S 表示起点城市，(1<=S<=N)
D 表示终点城市 ,(1<=D<=N)
L 表示道路的长度 (1<=L<=100)
C 表示经过该道路所需的过路费 (0<=C<=100)
对于每组数据输出一行，输出 McFn 能走的从城市 1 到城市 N 的最短路径的总长度。如果该路径不存在，输出-1。
1 5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
11
5 人解决，22 人已尝试。
11 份提交通过，共有 133 份提交。
8.8 EMB 奖励。