Mô tả bài toán

Nông dân John đang nghiên cứu một hợp đồng sữa mới ở một lãnh thổ mới. Anh ta dự định phân phối sữa đến T (1 ≤ T ≤ 25.000) thị trấn, được đánh số từ 1 đến T. Các kết nối giữa các thị trấn bao gồm:

• Đường bộ: Là các kết nối hai chiều, mỗi đường bộ có chi phí Cᵢ (0 ≤ Cᵢ ≤ 10.000).
• Chuyến bay: Là các kết nối một chiều (máy bay), mỗi chuyến bay có chi phí Cᵢ (-10.000 ≤ Cᵢ ≤ 10.000).

John có nhiệm vụ tìm chi phí tối thiểu để đi từ thị trấn S (điểm khởi hành) đến tất cả các thị trấn khác. Nếu không có cách nào để đi đến một thị trấn cụ thể, in ra "NO PATH".

Định dạng đầu vào

• Dòng 1: Bốn số nguyên cách nhau bởi dấu cách: T, R, P, S:

  • T: Số lượng thị trấn.
  • R: Số lượng đường bộ.
  • P: Số lượng chuyến bay.
  • S: Thị trấn khởi hành (1 ≤ S ≤ T).

• Dòng 2 đến R+1: Mỗi dòng gồm ba số nguyên Aᵢ, Bᵢ, Cᵢ:

  • Aᵢ và Bᵢ: Hai thị trấn được kết nối bởi đường bộ.
  • Cᵢ: Chi phí đi qua đường bộ này (hai chiều).

• Dòng R+2 đến R+P+1: Mỗi dòng gồm ba số nguyên Aⱼ, Bⱼ, Cⱼ:

  • Aⱼ: Thị trấn xuất phát của chuyến bay.
  • Bⱼ: Thị trấn đích của chuyến bay.
  • Cⱼ: Chi phí chuyến bay này (một chiều).

Định dạng đầu ra

• In T dòng, dòng thứ ~i~ chứa chi phí tối thiểu từ S đến thị trấn ~i~:
  • Nếu không có cách nào để đến thị trấn ~i~, in "NO PATH".

Ví dụ

Input:

6 3 4 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 1 -100
3 4 -100
1 3 -10

Output:

NO PATH
NO PATH
5
0
-95
-100