THỰC HÀNH

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 <= K < N, 1 <= M <= 10⁴).
  • 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 <= 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:
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:
55

Giải thích:

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