青少年C语言等级考试八级真题：道路（roads）。

N个以1…N标号的城市通过单向的道路相连，每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）。Bob过去住在城市1，在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径，前提是他能够付的起通行费。

时间限制：1000ms 内存限制：65536KB

输入

第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。 第二行包含整数N，2 <= N <= 100, 指城市的数目。 第三行包含整数R, 1 <= R <= 10000, 指路的数目。 接下来的R行，每行包含4个整数S, D, L, T，描述一条单向道路：

• S：道路起始城市，1 <= S <= N
• D：道路终点城市，1 <= D <= N
• L：道路长度，1 <= L <= 100
• T：通行费（金币数量），0 <= T <= 100

注意：不同的道路可能有相同的起点和终点。

输出

输出仅一行，即从城市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