Nhân dịp trúng tuyển vào đội tuyển dự thi học sinh giỏi quốc gia và cũng mới thi đỗ bằng lái xe máy nên Long được mẹ thưởng cho một buổi đi chơi. Long quyết định đến thăm nhà Trường là bạn thân của mình. Địa chỉ nhà Long và nhà Trường là hai trong số n nút giao thông trong thành phố. Có tất cả m tuyến đường hai chiều nối trực tiếp giữa các nút giao thông, giữa hai nút khác nhau bất kì có thể có nhiều tuyến đường nối trực tiếp. Tuyến thứ i nối trực tiếp giữa hai nút giao thông a_i và b_i, đi qua hết thời gian t_i và sẽ bị thu một khoản phí là h_i.

Long chỉ có số tiền bằng k để trả tiền phí đi đường, do cũng muốn mua quà cho bạn nên Long không thể để hết sạch tiền khi đến nhà Trường (khi đến nhà Trường số tiền còn lại phải lớn hơn 0). Ngoài ra, để có thời gian chơi với bạn nhiều hơn thì Long cần tìm đường đi từ nhà mình đến nhà Trường sao cho tổng thời gian đi là nhỏ nhất.

Yêu cầu: Hãy tìm đường đi từ nhà Long đến nhà Trường thoả mãn yêu cầu trên.

Dữ liệu: Vào từ file văn bản THAMNHA.INP theo khuôn dạng sau:

• Dòng thứ nhất chứa ba số tự nhiên k, n, m (k ≤ 200, n ≤ 2000, m ≤ 2.10⁶).
• Dòng thứ i trong số m dòng tiếp theo, mỗi dòng chứa bốn số nguyên a_i, b_i, t_i và h_i (1 ≤  a_i ≠ b_i ≤ n, 1 ≤ t_i ≤ 10⁵, 0 ≤ h_i ≤ 200).  
• Dòng cuối cùng chứa hai số nguyên a và b tương ứng  là  địa  chỉ  nhà  Long  và  nhà Trường (1 ≤  a ≠ b ≤ n).       

Kết quả: Ghi ra file văn bản THAMNHA.OUT một số nguyên là tổng thời gian nhỏ nhất của đường đi tìm được. Ghi ra số -1 nếu không tìm được đường đi thoả mãn yêu cầu.