Một chiếc xe điện thông minh xuất phát từ trạm \(S\) đi đến trạm đích \(T\) trên một bản đồ gồm \(N\) trạm và \(M\) con đường một chiều nối giữa các trạm. Xe có một mức dung lượng pin tối đa là \(C\). Mỗi con đường đi qua có trọng số tiêu hao năng lượng là \(w\) (nếu \(w > 0\) là hao hụt pin, nếu \(w < 0\) là xe được nạp thêm pin từ các đệm sạc từ tính lắp dưới đường).

Ngoài ra, có một số trạm sạc đặc biệt trong thành phố mà khi đi qua, xe điện sẽ tự động được nạp đầy pin lên mức tối đa \(C\) ngay lập tức. Mức pin tại trạm nguồn \(S\) ban đầu được nạp đầy bằng \(C\). Tại mọi thời điểm di chuyển trên đường, mức pin của xe phải luôn nằm trong khoảng từ \(0\) đến \(C\) (không bao giờ được nhỏ hơn \(0\), và lượng pin nạp thêm không được vượt quá \(C\)).

Hãy tìm một lộ trình di chuyển từ \(S\) đến \(T\) sao cho tổng lượng pin tiêu thụ (tổng trọng số \(w\) của các cạnh đi qua) là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa sáu số nguyên \(N, M, C, S, T\) và \(K\) (\(1 \le N \le 500\), \(1 \le M \le 2000\), \(1 \le C \le 100\), \(1 \le S, T \le N\), \(0 \le K \le N\)) với \(K\) là số lượng trạm sạc đặc biệt.
• Dòng thứ hai chứa \(K\) số nguyên mô tả chỉ số của các trạm sạc đặc biệt.
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(-25 \le w \le 25\)) mô tả con đường đi một chiều từ \(u\) đến \(v\) có trọng số tiêu hao pin \(w\).

Kết quả ra

• In ra một số nguyên duy nhất là tổng chi phí tiêu hao pin nhỏ nhất. Nếu không thể di chuyển từ \(S\) đến \(T\) thỏa mãn điều kiện pin, in ra \(-1\).

Ví dụ

Input

4 4 10 1 4 1
3
1 2 5
2 3 6
3 4 -2
1 4 9

Output

9