Mạng lưới giao thông thành phố gồm ~ n ~ nút được đánh số từ 1 đến ~ n ~ có ~ 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 tối đa 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

• Dòng đầu tiên chứa 5 số nguyên dương: ~ n, m , k, s, t~ ~(1≤s, 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 ~ d_i, c_i, l_i ~ cách nhau bởi dấu cách, trong đó ~ l_i ~ là độ dài của đường một chiều thứ ~ i ~ từ nút ~ d_i ~ đến nút ~ c_i ~.
• Dòng thứ ~ j ~ trong ~ k ~ dòng tiếp theo chứa 3 số nguyên dương ~ u_j, v_j~ và ~q_j ~ cách nhau bởi dấu cách, trong đó ~ q_j ~ là độ dài đường đi hai chiều được đề xuất thứ ~ j ~ nối hai nút ~ u_j ~ và ~ v_j ~.

Kết quả

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)

Ràng buộc

• ~ n≤1000 ~
• ~ k≤300 ~
• ~ 0≤l_i≤1000 ~
• ~ q_j ≤ 1000 ~

Ví dụ:

Input 1

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 1

35