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