Phát biểu bài toán

Gia đình Tuấn sống tại thành phố XYZ với ~ N ~ nút giao thông và ~ M ~ đường đi một chiều giữa các nút giao thông. Nhà Tuấn ở nút ~ 1 ~, cơ quan của mẹ Tuấn ở nút ~ K ~, và trường của Tuấn ở nút ~ N ~.

Mỗi đường ~ i ~ từ nút ~ u ~ đến nút ~ v ~ có hai thời gian di chuyển:

• ~ a_{ij} ~: Thời gian di chuyển bằng ô tô.
• ~ b_{ij} ~: Thời gian di chuyển bằng đi bộ.

Mẹ Tuấn chở Tuấn đến một nút giao thông nào đó bằng ô tô, sau đó Tuấn đi bộ đến trường. Hãy tìm thời gian tối thiểu để Tuấn đến trường mà mẹ Tuấn không bị muộn giờ làm.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên ~ N, M, K ~ (~ 1 \leq K < N ~, ~ 1 \leq M \leq 10^4 ~).
  • ~ N ~: Số nút giao thông.
  • ~ M ~: Số đường đi một chiều.
  • ~ K ~: Nút giao thông của cơ quan mẹ Tuấn.
• ~ M ~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên ~ u, v, a_{ij}, b_{ij} ~:
  • ~ u, v ~: Đường một chiều từ nút ~ u ~ đến nút ~ v ~.
  • ~ a_{ij} ~: Thời gian đi bằng ô tô (~ 0 < b_{ij} \leq a_{ij} ~).
  • ~ b_{ij} ~: Thời gian đi bộ.

Dữ liệu ra

• Một số nguyên duy nhất là thời gian tối thiểu để Tuấn đến trường mà mẹ Tuấn không bị muộn.

Ví dụ

Input (SCHOOL.INP)

5 6 3
1 4 60 40
1 2 60 30
2 3 60 30
4 5 30 15
4 3 19 10
3 5 20 10

Output (SCHOOL.OUT)

55

Giải thích:

• Mẹ Tuấn chở Tuấn từ nút ~ 1 \to 4 ~ (thời gian: ~ 60 ~).
• Tuấn đi bộ từ ~ 4 \to 5 ~ (thời gian: ~ 15 ~).
• Tổng thời gian: ~ 60 - 40 + 15 = 55 ~.