1973: 乘车路线
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Normal Judger
Creator：
Submit：2
Solved：0
Description
【问题描述】
编号为1.. N的N座城镇用若干仅供单向行驶的道路相连，每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）。
小智准备从城镇1出发到达城镇N，但他目前只有W的钱，为此，你需要帮助他寻找一条从城镇1到城镇N在他能支付的前提下的一条最短路线。
【输入格式】
第一行输入三个整数N、K、W（N为城镇数目，2<=N<=100，K为道路条数，1<=K<=10000,W为钱的数目，0<=w<=1000）
随后的 K 行每行为一条道路的信息，包含4个数值（S,D,L,T）其中S为源城镇，D为目标城镇，L为道路长度，T为所需支付用。（1<=S,D<=N,1<=L<=100,0<=T<=100）
【输出格式】
输出最短长度，若无解，则输出“NO”
【输入样例】
6 7 5
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
Input
第一行输入三个整数N、K、W（N为城镇数目，2<=N<=100，K为道路条数，1<=K<=10000,W为钱的数目，0<=w<=1000）
随后的K行每行为一条道路的信息，包含4个数值（S,D,L,T）其中S为源城镇，D为目标城镇，L为道路长度，T为所需支付用。（1<=S,D<=N,1<=L<=100,0<=T<=100）
Output
输出最短长度，若无解，则输出“NO”
Sample Input Copy
6 7 5
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 2Sample Output Copy
11