Giải cứu cô gái

Trong một buổi phỏng vấn, FullHouse Dev được đưa ra một bài toán thú vị về việc tối ưu hóa thời gian. Họ cần tìm ra cách nhanh nhất để nâng cao kỹ năng chiến đấu nhằm giải cứu một người đang gặp nguy hiểm.

Bài toán

FullHouse Dev cần giúp một người nâng cấp kỹ năng chiến đấu từ cấp độ \(X\) lên cấp độ \(Y\). Có nhiều phương pháp chuyển đổi khác nhau, mỗi phương pháp \(i\) sẽ giúp chuyển từ cấp độ \(Ai\) sang cấp độ \(Bi\) với chi phí thể lực là \(Zi\) (và ngược lại).

Tại mỗi cấp độ \(i\), có thể sử dụng một loại quả ác quỷ đặc biệt. Khi ăn quả này, người dùng sẽ ngủ trong \(Hi\) giờ và sau đó thể lực sẽ được đặt thành \(Ci\) (không cộng dồn vào thể lực hiện tại). Việc ăn quả là tùy chọn.

Nhiệm vụ là tìm ra thời gian ngủ tối thiểu cần thiết để đạt được cấp độ mục tiêu. Thể lực ban đầu là 0.

INPUT FORMAT:

• Dòng đầu tiên chứa 4 số nguyên \(N\) (số lượng cấp độ), \(M\) (số lượng phương pháp chuyển đổi), \(A\) (cấp độ ban đầu), \(B\) (cấp độ mục tiêu)
• \(M\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(X\), \(Y\), \(Z\) thể hiện có thể chuyển từ cấp độ \(X\) sang cấp độ \(Y\) với chi phí thể lực \(Z\)
• \(N\) dòng cuối, mỗi dòng chứa 2 số nguyên \(Ci\), \(Hi\), thể hiện tại cấp độ \(i\), có thể đặt thể lực thành \(Ci\) sau khi ngủ \(Hi\) giờ

OUTPUT FORMAT:

• Một số nguyên duy nhất là thời gian ngủ tối thiểu cần thiết. Nếu không thể đạt được mục tiêu, in ra -1.

Ràng buộc:

• \(1 \leq N \leq 1000\)
• \(0 \leq M \leq 1000\)
• \(1 \leq \text{Cấp\_độ\_ban\_đầu}, \text{Cấp\_độ\_mục\_tiêu} \leq N\)
• \(1 \leq Xi, Yi \leq N\)
• \(1 \leq Zi \leq 10^9\)
• \(1 \leq Ci, Hi \leq 10^9\)

Ví dụ

INPUT

3 3 1 3
1 2 2
1 3 3
3 2 1
2 7
2 7
3 6

OUTPUT

14

Giải thích

• Đầu tiên, ăn quả ác quỷ ở cấp độ 1 và ngủ 7 giờ để có thể lực 2
• Sau đó chuyển sang cấp độ 2, tốn 2 thể lực
• Tiếp tục ăn quả ác quỷ ở cấp độ 2 và ngủ 7 giờ để có thể lực 2
• Cuối cùng chuyển sang cấp độ 3 với chi phí 1 thể lực
• Tổng thời gian ngủ = 7 + 7 = 14 giờ