Nguyên là dân IT nên đặc biệt thích tiền điện tử. Nguyên rất quan tâm tới những đồng tiền điện tử mới, có hệ sinh thái rõ ràng và bắt đầu được niêm yết trên các sàn quốc tế lớn như Binance, Remitano, Bitget, …. Một buổi tối, mở zalo lên, Nguyên được một người bạn giới thiệu về đồng tiền ECOIN, với khả năng phán đoán siêu phàm về tương lai phát triển của đồng tiền này, không một chút lưỡng lự, Nguyên quyết định đi gặp một số đầu mối đang nắm giữ đồng tiền này để mua lại đầu tư.

Đất nước của Nguyên ở có ~N~ thành phố được đánh số từ ~1~ đến ~N~, nối với nhau bởi ~M~ con đường hai chiều, mỗi con đường nối một cặp thành phố khác nhau và mỗi cặp thành phố có không quá một con đường nối trực tiếp. Nguyên ở thành phố ~A~, bạn của Nguyên ở thành phố ~B~ ~(A \ne B)~. Qua thông tin từ bạn bè và Internet cung cấp Nguyên biết danh sách ~K~ thành phố có giao dịch đồng tiền này và giá bán ở mỗi thành phố có thể khác nhau. Qua Internet cũng cho biết để đi từ thành phố ~i~ tới thành phố ~j~ mất chi phí là ~d_{ij}~ nếu hai thành phố này có đường nối trực tiếp.

Nguyên quyết định lái xe đi từ thành phố ~A~ đến thành phố ~B~ và sẽ mua đồng tiền ECOIN ở một trong số các thành phố trên đường đi. Vấn đề là phải chọn đường đi sao cho tổng chi phí trên đường đi cộng với chi phí mua đồng tiền ECOIN là nhỏ nhất. Mỗi thành phố, mỗi cung đường có thể đi qua nhiều hơn ~1~ lần.

Yêu cầu: Xác định tổng chi phí nhỏ nhất để thực hiện kế hoạch của Nguyên.

Input

• Dòng ~1~: chứa ~3~ số nguyên dương ~N, M, K~ ~(2 \le N \le 5000; 1 \le M \le 100000; 1 \le K \le N)~;

• Dòng ~2~: chứa hai số ~A, B~ ~(1 \le A, B \le N)~;

• Dòng ~3~: chứa ~K~ cặp số nguyên dương, mỗi cặp xác định thành phố và giá bán đồng tiền ECOIN (nằm trong phạm vi từ ~1~ đến ~10^9~).

• Mỗi dòng trong ~M~ dòng tiếp theo chứa ~3~ số nguyên ~i, j, d_{ij}~ ~(1 \le d_{ij} \le 10^5)~

Lưu ý: dữ liệu đảm bảo luôn có đường đi giữa hai thành phố bất kỳ.

Output

Một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Scoring

Sample Input 1

5 7 4
1 4
1 100 4 50 3 10 2 55
1 2 10
5 3 42
1 3 30
2 4 50
3 4 70
2 5 24
4 5 21

Sample Output 1

103