Submit solution


Points: 0.17 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Central European Olympiad in Informatics '98
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ thành phố ~1~ ...~N~ nối bởi các con đường một chiều. Mỗi con đường có hai giá trị: độ dài và chi phí phải trả để đi qua. Bob ở thành phố ~1~. Bạn hãy giúp Bob tìm đường đi ngắn nhất đến thành phố ~N~, biết rằng Bob chỉ có số tiền có hạn là ~K~ mà thôi.

Input

Dòng đầu tiên ghi ~t~ là số test. Với mỗi test:

  • Dòng đầu ghi ~K~ (~0 \leq K \leq 10000~).
  • Dòng ~2~ ghi ~N~, ~2 \leq N \leq 100~.
  • Dòng ~3~ ghi ~R~, ~1 \leq R \leq 10000~ là số đường nối.
  • Mỗi dòng trong ~R~ dòng sau ghi ~4~ số nguyên ~S~, ~D~, ~L~, ~T~ mô tả một con đường nối giữa ~S~ và ~D~ với độ dài ~L~ (~1 \leq L \leq 100~) và chi phí ~T~ (~0 \leq T \leq 100~). Lưu ý có thể có nhiều con đường nối giữa hai thành phố.

Output

Với mỗi test, in ra độ dài đường đi ngắn nhất từ ~1~ đến ~N~ mà tổng chi phí không quá ~K~. Nếu không tồn tại, in ra ~-1~.

Sample Input

2
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
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0

Sample Output

11
-1

Comments

Please read the guidelines before commenting.



  • -7
    thefrog   commented on March 1, 2022, 9:34 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -11
    MrMinhFly   commented on May 26, 2021, 10:24 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -28
    SSLios23   commented on May 21, 2021, 4:48 p.m. edit 5

    This comment is hidden due to too much negative feedback. Show it anyway.