(thanhlee.*)

Nhà Thanh ở thành phố \(A\), nhà Lê ở thành phố \(B\), cuối tuần Thanh và Lê được nghỉ nên Thanh quyết định đến thành phố \(B\ \)để thăm Lê. Tuy nhiên Thanh chỉ có \(K\) đồng nên rất có thể Thanh phải đi xe buýt đến \(B\). Việc di chuyển qua nhiều thành phố có thể mất nhiều thời gian do vậy bạn hãy giúp Thanh tìm ra một hành trình đi từ \(A\) đến \(B\) sao cho thời gian di chuyển là ít nhất và Thanh vẫn còn tiền khi đến \(B\). Biết rằng:

Có \(N\) thành phố được đánh số từ 1 đến \(N\) (bao gồm cả \(A\) và \(B\)), giữa hai thành phố \(u\) và \(v\) có thể thể có tuyến xe buýt hoặc không, nếu có thì bạn được biết từ thành phố \(u\ \)đến \(v\) đi bằng xe buýt sẽ mất \(t\) thời gian và tốn \(x\) đồng.

Dữ liệu vào:

+ Dòng đầu tiên ghi 3 số nguyên \(K,\ N,\ M\) cho biết \(K\ \)là số đồng mà Thanh có, \(N\) là số lượng thành phố, \(M\) là số lượng các cặp thành phố có tuyến xe buýt.

+ \(M\) dòng tiếp theo mỗi dòng ghi 4 số nguyên \(u,\ v,\ t,\ x\) cho biết thông tin về tuyến xe buýt giữa thành phố \(u\) và \(v\) mất \(t\) thời gian và \(x\) đồng.

+ Dòng cuối cùng ghi hai số nguyên \(A\) và \(B\)

Các số trên cùng 1 dòng cách nhau ít nhất 1 ký tự trắng.

Kết quả: Một số nguyên thỏa yêu cầu của bài toán, nếu không có cách đi thì in ra số -1.

Giới hạn:

+ Trong tất cả test: \(1 \leq K \leq 200;\ 2 \leq N \leq 2000;1 \leq M \leq 10^{4};1 \leq t \leq 10^{5};0 \leq \ x\ \leq 200\)

+ Có 20% số điểm tương ứng với \(K = 1\ \)và \(N \leq 200\)

+ Có 20% số điểm tương ứng với \(K = 1\) và \(200 < N \leq 2000\)

Ví dụ: