Chuyến xe cứu trợ đồng bào Miền Bắc sau cơn bão Yagi được xuất phát tại Thanh Hoá đi qua các thành phố như Ninh Bình, Hà Nam,… một cách rất nhanh chóng. Nhưng khi xe đi vào thủ đô Hà Nội thì trời mưa to, một số tuyến phố bị ngập sâu. Thủ đô Hà Nội có hệ thống giao thông gồm n nút giao thông và m con đường hai chiều. Con đường thứ i (i=1..m) nối trực tiếp giữa hai nút giao thông ui, vi có độ ngập sâu là hi và thời gian đi qua là ti (ti không phụ thuộc vào hi), tất nhiên nếu tuyến đường ngập quá sâu thì xe sẽ gặp khó khăn khi đi qua.

Yêu cầu: Tìm hành trình để xe di chuyển từ nút giao thông X đến nút giao thông Y sao cho độ ngập sâu nhất trong tất cả các con đường đi qua là nhỏ nhất. Nếu có nhiều hành trình như vậy thì tìm hành trình có tổng thời gian di chuyển bé nhất. Biết rằng các con đường được thiết kế để luôn tồn tại hành trình từ X đến Y.

Dữ liệu: Vào từ tệp văn bản YAGI.INP gồm:

• Dòng đầu tiên ghi 3 số nguyên dương n, X, Y (X, Y ≤ n ≤ 105);
• Dòng tiếp theo là số nguyên dương m (m ≤ 106);

• Dòng thứ i trong m dòng tiếp theo (i=1..m) ghi bốn số nguyên dương ui, vi, hi, ti (ui, vi ≤ n; hi, ti ≤ 109).

  Dữ liệu: Ghi ra file văn bản YAGI.OUT gồm:

• Dòng thứ nhất ghi một số nguyên dương là độ sâu thoả mãn yêu cầu bài toán;

• Dòng thứ hai ghi tổng thời gian di chuyển của hành trình tìm được.

  Ví dụ:

  YAGI.INP            YAGI.OUT
  6 2 4               300
  10                  800
  2 1 900 100
  5 2 400 700
  1 5 200 600
  6 3 200 200
  4 5 100 100
  2 6 300 400
  1 6 500 200
  6 5 200 300
  3 4 200 300
  3 5 300 100
  

  Giải thích: Không có hành trình nào mà tất cả con đường đi qua có độ ngập sâu bé hơn 300 và trong số các hành trình đi qua con đường ngập sâu 300 thì hành trình có thời gian ngắn nhất là 2  6  5  4 với thời gian là 800.

Ràng buộc:

• Có 3 điểm có: hi=1 với mọi i =1..m;
• Có 3 điểm còn lại không có ràng buộc gì thêm.