2017: 过马路

城市中有R条有向马路，n个马路连接点，通过每条马路都要花去一定费用。你现在在编号为1的连接点，手里有k元钱，要去n号连接点的最短路径的长度是多少？途中经过道路的花费不能超过k。注意：两个马路连接点间可能有多条马路

第一行，k(0 <= K <= 10000)

第二行，n(2 <= N <= 100)

第三行，R(1 <= R <= 10000

以下R行

x y L t  从x到y的马路，长度L(1<=每条马路的长度<=100)，花费t(0<=每条马路的费用<=100)

满足条件最短路长度

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