#598. MANGGT - Mạng giao thông

Mạng lưới giao thông thành phố gồm nút được đánh số từ đến và đường một chiều nối 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 và khác nhau, một danh sách gồm đường hai chiều được đề xuất để xem xét xây dựng.

Nhiệm vụ của bạn là viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất giữa và (từ tới ) là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa năm số nguyên dương cách nhau bởi dấu cách;
• dòng tiếp theo, mỗi dòng chứa ba số nguyên dương cách nhau bởi dấu cách, trong đó là độ dài của đường một chiều từ nút đến nút ;
• dòng tiếp theo, mỗi dòng chứa ba số nguyên dương và cách nhau bởi dấu trống, trong đó là độ dài của đường hai chiều được đề xuất để nối giữa hai nút và .

Dữ liệu ra:

• Một dòng duy nhất, ghi ra độ dài nhỏ nhất có thể của đường đi ngắn nhất giữ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ừ đến , ghi .

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

35