Đề bài: Tìm chi phí tối thiểu để giao hàng

Nông dân John đang tiến hành 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 \leq T \leq 25,000 ~) thị trấn được đánh số thuận tiện là ~ 1 ~ đến ~ T ~. Thị trấn ~ S ~ (~ 1 \leq S \leq T ~) là trung tâm phân phối.

Thị trấn được kết nối bằng ~ R ~ con đường (~ 1 \leq R \leq 50,000 ~) và ~ P ~ chuyến bay (~ 1 \leq P \leq 50,000 ~), mỗi cái được mô tả với một chi phí ~ C_i ~.

• Các con đường ~ A_i, B_i, C_i ~ cho phép di chuyển hai chiều giữa ~ A_i ~ và ~ B_i ~.
• Các chuyến bay ~ A_i, B_i, C_i ~ chỉ có thể đi một chiều từ ~ A_i ~ đến ~ B_i ~.

Chi phí có thể âm hoặc dương (~ -10,000 \leq C_i \leq 10,000 ~), nhưng không có chu trình âm nào xuất hiện trên đồ thị. Nếu không thể đến được một thị trấn từ ~ S ~, trả về NO PATH.

Input

• Dòng 1: 4 số nguyên ~ T, R, P, S ~, với:
  • ~ T ~: Số thị trấn.
  • ~ R ~: Số con đường.
  • ~ P ~: Số chuyến bay.
  • ~ S ~: Trung tâm phân phối.
• Dòng 2 đến ~ R+1 ~: Mỗi dòng chứa 3 số nguyên ~ A_i, B_i, C_i ~, mô tả một con đường.
• Dòng ~ R+2 ~ đến ~ R+P+1 ~: Mỗi dòng chứa 3 số nguyên ~ A_i, B_i, C_i ~, mô tả một chuyến bay.

Output

• Xuất ~ T ~ dòng, mỗi dòng là chi phí tối thiểu để đi từ thị trấn ~ S ~ đến từng thị trấn ~ i ~. In NO PATH nếu không có cách nào đi đến thị trấn đó.

Ví dụ

Input

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

Output

NO PATH
NO PATH
5
0
-95
-100

Giải thích

• Chi tiết đầu vào:
  • Có 6 thị trấn.
  • Các con đường nối:
  • ~ 1 \leftrightarrow 2 ~: Chi phí 5.
  • ~ 3 \leftrightarrow 4 ~: Chi phí 5.
  • ~ 5 \leftrightarrow 6 ~: Chi phí 10.
  • Các chuyến bay một chiều:
  • ~ 3 \to 5 ~: Chi phí -100.
  • ~ 4 \to 6 ~: Chi phí -100.
  • ~ 1 \to 3 ~: Chi phí -10.
• Chi tiết đầu ra:
  • Không có cách nào đi từ ~ 4 ~ (trung tâm) đến ~ 1 ~ hoặc ~ 2 ~.
  • Từ ~ 4 ~ đến ~ 3 ~: Chi phí là ~ 5 ~.
  • Từ ~ 4 ~ đến chính nó: Chi phí ~ 0 ~.
  • Từ ~ 4 ~ đến ~ 5 ~: Chi phí ~ -95 ~.
  • Từ ~ 4 ~ đến ~ 6 ~: Chi phí ~ -100 ~.