SP338 ROADS - Roads

题面描述 有标号为 $1 \ldots n$ 的城市与单行道相连。对于每条道路有两个与之相关的参数：道路的长度以及需要支付的费用（用硬币的数量表示） 鲍勃和爱丽丝曾经生活在城市 $1$。在注意到爱丽丝在他们喜欢玩的卡牌游戏中作弊后，鲍勃决定与爱丽丝分手并搬走——去城市 $n$。他希望尽快到达那里——越快越好，然而他现在有些现金短缺。 我们希望帮助鲍勃找到从城市 $1$ 到城市 $n$ 的一条最短路径——但他必须用他现有的钱支付得起。

输入的第一行含有一个整数 $t$ 代表测试样例的组数。下面是t组测试样例。 对于每组测试数据，第一行含有一个整数 $K$（$0 \le K \le 10000$)，代表鲍勃所能支付得起的最大费用。 第二行含有一个整数 $N$（$2 \le N \le 100$)，代表城市总数。 第三行含有一个整数 $R$（$1 \le R \le 10000$)，代表道路的总数。 接下来 $R$ 行每行用四个整数 $S$、$D$、$L$、$T$，以单个空格分隔： $S$ 表示出发点城市标号（$1 \le S \le N$）； $D$ 表示目的地城市标号（$1 \le D \le N$）； $L$ 是该道路的长度（$1 \le L \le 100$）； $T$ 表示经过该道路的费用（$0 \le T \le 100$）。 注意不同的道路可能拥有相同的起点和终点。

对于每组测试样例，输出单独的一行表示当花费小于等于 $K$ 时最短路径的长度。如果不存在这样的路径，输出 $-1$。