描述
现在有N个城市，编号分别为1到N，他们之间用单向道路进行相连。值得注意的是，每条道路有2个参数：道路长度和需要为此道路支付的通行费。
现在周末来了，住在城市1的小明，拿上了他的钱包和他的switch，准备和小红一起玩1小时游戏。但是小红住在城市N，且小明的零花钱有限。
需要聪明的你帮助小明找到从城市1到城市N的最短路径，而且他能付得起这个通行费。
输入格式
第1行输入K。 这是小明拥有的零花钱K元。
第2行输入N。这是城市总数N。
第3行输入M。这是城市之间的单向道路数。
接下来的M行，每行输入一道道路，道路信息包含4个数字，分别代表每条道路的4个信息：S, D, L, C。
S为道路的起点（城市编号），D为道路终点（城市编号）， L为该道路的长度，C为该道路的通行费。
依次类推，输入若干组样例。
输出格式
第1行输出第1个样例的结果，1个数字。代表小明从城市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
数据范围
0 <= K <= 10000,
2 <= N <= 100,
1 <= M <= 10000,
这个是路径规划问题，可以参考一下：https://blog.csdn.net/YF_Li123/article/details/74090301
如果对你有帮助，可以点击我这个回答右上方的【采纳】按钮，给我个采纳吗，谢谢