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 các cặp nút. Với ý định muốn giảm được độ dài của đường đi ngắn nhất từ nút trọng yếu ~S~ đến nút ~T~ ~(S \neq T)~, một danh sách gồm ~K~ đường hai chiều được đề xuất để xem xét xây dựng.

Yêu cầu: 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 từ ~S~ đến ~T~ là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa năm số nguyên dương ~N~ ~(N \le 10^4)~, ~M~ ~(M \le 10^5)~, ~K~ ~(K \lt 300)~, ~S~ ~(S \le N)~, ~T~ ~(T \le N)~.

• Trên ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~A_i~, ~B_i~, ~L_i~. Trong đó ~L_i~ là độ dài của đường một chiều thứ ~i~ từ nút ~A_i~ đến nút ~B_i~ ~(L_i \le 1000)~.

• Trên ~K~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên dương ~U_j~, ~V_j~, ~Q_j~. Trong đó ~Q_j~ là độ dài của đường hai chiều được đề xuất thứ ~j~ nối giữa hai nút ~U_j~ và ~V_j~ ~(Q_j \le 1000)~.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Output

In độ dài nhỏ nhất có thể của đường đi ngắn nhất từ ~S~ đến ~T~ sau khi xây dựng xong một con đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ ~S~ đến ~T~ thì in ~-1~.

Sample Input 1

4 5 3 1 4
1 2 13
2 3 10
3 1 15
3 4 16
4 1 18
1 3 21
2 3 5
2 4 20

Sample Output 1

33