Gửi bài giải


Điểm: 0,17 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Central European Olympiad in Informatics '98
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -13
    trongtenlinhcbhk64  đã bình luận lúc 30, Tháng 4, 2023, 10:18

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -24
    thefrog  đã bình luận lúc 1, Tháng 3, 2022, 14:34

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -27
    MrMinhFly  đã bình luận lúc 26, Tháng 5, 2021, 3:24

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -49
    SSLios23  đã bình luận lúc 21, Tháng 5, 2021, 9:48 sửa 5

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.