UBND TP.Hồ Chí Minh có kế hoạch trong năm 2018 sẽ mở thêm một tuyến đường 2 chiều để rút ngắn khoảng cách và giảm ùn tắc giao thông giữa sân bay Tân Sơn Nhất đến trung tâm khu đô thị mới Thủ Thiêm cần sự giúp đỡ của các bạn Grokker!

Với qui hoạch hiện tại, mạng lưới giao thông bao gồm n điểm (từ 1 đến n) và có m đường 1 chiều nối n điểm lại với nhau. Một số nhà đầu tư đã đề xuất k giải pháp để xây dựng thêm đường 2 chiều trên để rút ngắn khoảng cách giữa 2 sân bay và trung tâm đô thị mới nhưng chính quyền thành phố đang phân vân không biết lựa chọn giải pháp nào là tối ưu nhất.

Các bạn hãy giúp UBND thành phố lựa chọn phương án tối ưu nhất để giảm thiểu chi phí xây dựng và góp phần giảm ùn tắc giao thông nhé!

Bên dưới là một bộ input mẫu, các bạn có thể xem link bên dưới đễ rõ hơn nhé. Dòng đầu tiên lần lượt là n, m, k, s, t. Với m dòng tiếp theo, mỗi dòng gồm 3 số theo thứ tự là di, ci, li cho biết đường 1 chiều từ di đến ci có độ dài li. k dòng còn lại theo thứ tự là uj, vj, qj cho biết k đường 2 chiều đã được đề xuất từ uj đến vj có độ dài qj.

Input
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

Output
35

Bạn hãy chọn 1 trong các phương án xây dựng đường 2 chiều để quãng đường từ s đến t là ngắn nhất và cho biết độ dài quãng đường ngắn nhất đó là bao nhiêu?

Các bạn có thểm submit solution của mình tại đây: http://r.grokking.org/spoj-problems-trafficn

Hãy cùng nhau góp phần xây dựng thành phố ngày càng văn minh, hiện đại hơn nhé!