当前没有测试数据。

题目描述

$N$ 个以 $1 \sim N$ 标号的城市通过单向的道路相连，每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）。

Bob 和 Alice 过去住在城市 $1$，在注意到 Alice 在他们过去喜欢玩的纸牌游戏中作弊后，Bob 和她分手了，并且决定搬到城市 $N$。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助 Bob 找到从 $1$ 到 $N$ 最短的路径，前提是他能够付的起通行费。

输入格式

第一行包含一个整数 $K$，$0 \le K\le 10000$，代表 Bob 能够在他路上花费的最大的金币数。

第二行包含整数 $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 <= N$，$L$ 是道路长度，$1 \le L \le 100$，$T$ 是通行费（以金币数量形式度量），$0 \le T \le100$。注意不同的道路可能有相同的起点和终点。

输出格式

输入结果应该只包括一行，即从城市 $1$ 到城市 $N$ 所需要的最小的路径长度（花费不能超过 $K$ 个金币）。如果这样的路径不存在，结果应该输出 $-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