#776. Đường bộ và Đường hàng không (ROADPLANE)

Farmer John đang khảo sát phương án bán sữa tại một khu vực mới. Ông muốn gửi sữa đến thị trấn, được đánh số từ đến . Các thị trấn này được kết nối bởi con đường bộ (đánh số từ đến ) và đường bay (đánh số từ đến ). Mỗi con đường bộ hoặc đường bay nối thị trấn đến với chi phí là .

Đối với đường bộ, . Tuy nhiên, chi phí đường bay rất kỳ lạ, chi phí có thể là số âm. Đường bộ là hai chiều, có thể đi từ đến hoặc từ đến với cùng chi phí . Ngược lại, đường bay là một chiều, chỉ có thể đi từ đến .

Thực tế, do tình hình an ninh gần đây, có một số chính sách đảm bảo rằng: Nếu có một đường bay từ đến , thì đảm bảo không thể quay lại từ thông qua bất kỳ con đường bộ hay đường bay nào. Vì thế giới bò sữa của FJ được công nhận là rất mạnh mẽ, ông cần vận chuyển bò đến mọi thị trấn. Ông muốn tìm phương án rẻ nhất để vận chuyển bò từ thị trấn trung tâm phân phối đến từng thị trấn khác, hoặc biết rằng điều đó là không thể.

Dữ liệu:

• Dòng đầu tiên chứa bốn số nguyên cách nhau bởi dấu cách: .
• Từ dòng thứ 2 đến dòng : Ba số nguyên cách nhau bởi dấu cách (mô tả một con đường bộ): và .
• Từ dòng đến dòng : Ba số nguyên cách nhau bởi dấu cách (mô tả một đường bay): và .

Kết quả:

• Xuất ra dòng, dòng thứ biểu thị chi phí nhỏ nhất để đến thị trấn . Nếu không tồn tại đường đi, xuất ra NO PATH.

Ví dụ:

Dữ liệu:

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

Kết quả:

NO PATH
NO PATH
5
0
-95
-100

Giới hạn: .

• Đảm bảo với mọi đường bộ: .
• Với mọi đường bay: .