Hệ thống giao thông thành phố Định Nam gồm ~n~ nút giao thông đánh số ~1,2, … , n~ kết nối bởi ~m~ đường hai chiều, mỗi con đường tốn thời gian di chuyển nhất định, lượng thời gian này đúng với mọi phương tiện giao thông vì thành phố quy định tốc độ di chuyển cố định trong toàn hệ thống.

Trong kỳ thi chọn HSG tỉnh, Nam cần di chuyển từ nút giao thông ~s~ đến nút giao thông ~t~. Tuy nhiên, khi chuẩn bị xuất phát thì cậu mới biết do có đoàn ngoại giao nước ngoài đến làm việc nên một số con đường sẽ bị chặn tạm thời. Cụ thể, hành trình của đoàn ngoại giao là ~(w_1, w_2, … , w_3)~ hành trình này đảm bảo thông suốt và không có con đường nào xuất hiện quá một lần.

Đối với mỗi con đường trong hành trình, tạm kí hiệu là ~(𝑎, 𝑏)~, kể từ khi đoàn ngoại giao xuất hiện ở ~𝑎~ cho đến khi ra khỏi ~𝑏~, không có phương tiện nào được phép tiến vào cả từ ~𝑎~ lẫn ~𝑏~, các phương tiện có mặt trên đường từ trước đó vẫn có thể tham gia giao thông như bình thường. Nam xuất phát muộn hơn đoàn ngoại giao ~𝑘~ phút, hãy xác định thời điểm cậu đến đích sớm nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên ~𝑛, 𝑚~ ~(2 ≤ 𝑛 ≤ 10^3 ; 2 ≤ 𝑚 ≤ 10^4)~.
• Dòng thứ hai ghi bốn số nguyên ~𝑠,t, 𝑘, 𝑐~ ~(0 ≤ 𝑘, 𝑐 ≤ 10^3)~.
• Dòng thứ 3: ~𝑐~ số nguyên ~w_1, w_2, … , w_3~.
• Các dòng 4 … ~𝑚 + 3~: mỗi dòng ba số nguyên ~𝑢, 𝑣, 𝑙~ ~(1 ≤ 𝑙 ≤ 10^3)~ thể hiện một con đường nối hai nút giao thông ~𝑢, 𝑣~ tốn thời gian di chuyển ~𝑙~ phút, không có cặp nút giao thông nào được nối bởi nhiều hơn một con đường.

Kết quả

• Một số nguyên là số phút di chuyển tối thiểu của Nam.

Ví dụ

Input1:

6 5 
1 6 20 4 
5 3 2 4 
1 2 2 
2 3 8 
2 4 3 
3 6 10 
3 5 15 

Output1:

21 

Input2:

8 9 
1 5 5 5 
1 2 3 4 5 
1 2 8 
2 7 4 
2 3 10 
6 7 40 
3 6 5 
6 8 3 
4 8 4 
4 5 5 
3 4 23 

Output2:

40