TRAFFICN

Nguồn bài: http://vn.spoj.com/problems/TRAFFICN/

Mạng lưới giao thông thành phố gồm N nút được đánh số từ 1 đến N và m đường một chiều nối giữa các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu s và t khác nhau, một danh sách gồm k đường hai chiều được đề xuất để xem xét xây dựng

Nhiệm vụ của bạn là chọn 1 đường hai chiều trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi giữa s và t là nhỏ nhất

Dữ liệu vào: từ file TRAFFICN.INP

+ Dòng đầu tiên  chứa 5 số nguyên dương: N (N≤1000), m , k (k≤300), s (1≤s≤N), t (1≤t≤N) cách nhau bởi dấu cách.

+ Dòng thứ i trong m dòng tiếp theo chứa 3 số nguyên dương di, ci, li cách nhau bở dấu cách, trong đó li là độ dài (0≤li≤1000) của đường một chiều thứ i từ nút di đến nút ci. Dòng thứ j trong k dòng tiếp theo chứa 3 số nguyên dương uj, vj và qj (qj≤1000) cách nhau bởi dấu cách, trong đó qj là độ dài đường đi hai chiều được đề xuất thứ j nối hai nút uj và vj.

Dữ liệu ra: ghi vào file TRAFFICN.OUT là một số nguyên duy nhất là độ dài nhỏ nhất có thể của đường đi ngắn nhất của hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ s đến t ghi -1

(Không nhất thiết phải có đường 2 chiều trong đường đi ngắn nhất)

TĂNG GIỚI HẠN CỦA N VÀ M KHI DÙNG DIJKSTRA HEAP

Ví dụ:

TRAFFICN.INP	TRAFFICN.OUT
4 5 3 1 4 1 2 13 2 3 19 3 1 25 3 4 17 4 1 18 1 3 23 2 3 5 2 4 25	35

TEST