와인 배송

사업가 종원은 새로운 지역에서 신규 와인 계약을 위한 연구를 진행하고 있습니다. 그는 1..R까지 번호가 매겨져있는 최대 R (1 <= R <= 50,000)개의 도로와 1..P까지 번호가 매겨져있는 최대 P (1 <= P <= 50,000)개의 비행기 노선으로 연결되어 있는 T (1 <= T <= 25,000)개의 마을에 와인을 납품하려고 합니다.

도로 i 또는 비행기 i가 마을 A_i (1 <= A_i <= T)에서 마을 B_i (1 <= B_i <= T)를 이동하는데 드는 비용은 C_i입니다. 도로의 경우, 0 <= C_i <= 10,000; 이지만, 항공사의 재정 상황 때문에 비행기의 비용은 음수가 될 수 있습니다 (-10,000 <= C_i <= 10,000).

도로는 양방향이며, A_i에서 B_i로 또는 B_i에서 A_i로 같은 비용으로 이동할 수 있습니다; 도로의 비용은 반드시 0이상이어야 합니다.

그러나, 비행기는 입력에서 명시된대로 A_i에서 B_i로만 사용할 수 있습니다. 예를 들어, A_i에서 B_i로 가는 비행기가 있으면, 테러 방지 규정 때문에 B_i에서 A_i로 돌아갈 수 있는 어떠한 도로와 비행기 노선 조합도 존재하지 않습니다.

사업가 종원은 세계 최고급 와인의 공급을 제공하는 사람으로 전 세계에 알려져 있습니다. 실제로 그는 모든 마을에서 와인 주문을 받고 있습니다. 그래서 그는 마을 S (1 <= S <= T)에 위치한 배송 센터에서 각 마을로 배달하는 가장 저렴한 가격을 찾고 싶어합니다. 또는 배송이 불가능한 경우 이를 알고 싶어합니다.

• 첫 번째 줄: 네 개의 공백으로 구분된 정수: T, R, P, 그리고 S
• 두 번째 줄부터 R+1 번째 줄: 도로를 설명하는 세 개의 공백으로 구분된 정수: A_i, B_i 그리고 C_i
• R+2 번째 줄부터 R+P+1 번째 줄: 비행기를 설명하는 세 개의 공백으로 구분된 정수: A_i, B_i 그리고 C_i

• 첫 번째 줄부터 T 번째 줄: 배송 센터 S에서 마을 i로 가는 최소 비용, 또는 이것이 불가능한 경우 'NO PATH'