Hệ thống giao thông thành phố Định Nam gồm 𝑛 nút giao thông đánh số 1,2, … , 𝑛 kết nối bởi 𝑚 đườ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 DHBB, Nam cần di chuyển từ nút giao thông 𝑠 đến nút giao thông 𝑡. 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_c) 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

Dòng 1: hai số nguyên 𝑛, 𝑚 (2 ≤ 𝑛 ≤ 10^3; 2 ≤ 𝑚 ≤ 10^4 ).

Dòng 2: bốn số nguyên 𝑠, t, 𝑘, 𝑐 (0 ≤ 𝑘, 𝑐 ≤ 10^3).

Dòng 3: 𝑐 số nguyên w_1, w_2, … , w_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ả

Dòng 1: Số nguyên là số phút di chuyển tối thiểu của Nam.

Sample Input

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

Sample Output

21

Sample Input

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

Sample Output

40

Giới hạn

 30% số điểm của bài tương ứng với 1 ≤ m ≤ 1000.
30% số điểm của bài tương ứng với 1000 < m ≤ 5000.
40% số điểm còn lại không có rằng buộc gì thêm.