Ở một nơi rất xa có một quần đảo gồm có ~n~ hòn đảo được đánh số từ 1 đến ~n~. Có ~m~ tuyến đường biển để đi lại hai chiều giữa các đảo, tuyến đường thứ ~i~ nối hai đảo khác nhau ~u_i, v_i~ (~1 \le u_i, v_i \le n~) và mất ~t_i~ đơn vị thời gian để đi hết nó.

Để đi lại giữa các đảo, chúng ta sử dụng tàu thủy có độ dày thân tàu là ~k~ cm. Mỗi khi tàu đi hết tuyến đường ~i~, thân tàu bị làm mòn ~h_i~ cm. Như vậy, để đi từ đảo A đến đảo B với tàu thủy có độ dày thân tàu là ~k~ cm bằng các tuyến đường thì tổng độ làm mòn thân tàu trên các tuyến đường mà nó đi qua phải nhỏ hơn ~k~.

Yêu cầu: Cho trước hai hòn đảo A và B (~1 \le A, B \le n, A \ne B~). Tìm đường đi cho con tàu khi đi từ đảo A tới đảo B có tổng thời gian là ít nhất (thỏa mãn có tổng độ làm mòn thân tàu khi đi trên đường đi này nhỏ hơn ~k~).

Input

• Dòng thứ nhất gồm 3 số nguyên ~k, n, m~ (~1 \le k \le 200, 2 \le n \le 10000, 1 \le m \le 100000~), mỗi số cách nhau một dấu cách.
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên ~u_i, v_i, t_i, h_i~ (~1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le t_i \le 10^5, 0 \le h_i \le 200~) thể hiện đi lại trên tuyến đường thứ ~i~ nối hai đảo ~u_i, v_i~ mất ~t_i~ đơn vị thời gian và độ làm mòn thân tàu khi đi trên nó là ~h_i~.
• Dòng cuối cùng chứa hai số nguyên ~A~ và ~B~ (~1 \le A, B \le n, A \ne B~).

Output

• Một số nguyên duy nhất là thời gian ít nhất khi đi từ đảo A tới đảo B thỏa mãn yêu cầu trên hoặc đưa ra -1 nếu không có cách đi từ đảo A tới đảo B.