Baoma là tổng thống của đất nước mà Ben đang sinh sống. Một ngày nọ, Baoma đi thăm thành phố mà Ben làm việc, và để đảm bảo an ninh, một số giao thông bị xáo trộn, làm ảnh hưởng đến đời sống nhân dân, và công việc trở hàng của Ben cũng gặp chút vấn đề.

Khi Baoma di chuyển trên một con đường nào đó, cảnh sát sẽ chặn 2 đầu đường và không cho phép bất cứ ai đi vào con đường trước khi Baoma đi ra khỏi con đường đó, tuy nhiên, những ai đã đi vào con đường đó trước khi Baoma đi vào vẫn có thể tiếp tục di chuyển và rời khỏi con đường này.

Ben vẫn cố gắng công việc trở hàng của mình. Anh biết trước lịch trình của Baoma, và tính toán kĩ kế hoạch cho mình. Thành phố được mô phỏng bằng các nút giao thông và các con đường 2 chiều.

Yêu cầu: Hãy viết chương trình tính toán thời gian tối thiểu để Ben hoàn thành công việc của mình. Biết rằng Baoma xuất phát trước Ben ~k~ phút.

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ (~1 \le n \le 10^5~, ~1 \le m \le 2 \times 10^5~), trong đó ~n~ là số nút giao thông của thành phố, ~m~ là số con đường.
• Dòng thứ 2 chứa 4 số nguyên ~a, b, k~ và ~g~ (~1 \le a, b, g \le n~, ~1 \le k \le 10^3~), với ~a~ và ~b~ là nút giao thông mà Ben xuất phát và nút giao thông Ben đến, ~k~ là chênh lệch thời gian xuất phát của Baoma và Ben, ~g~ là số nút giao thông trên đường đi của Baoma.
• Dòng thứ 3 chứa ~g~ số nguyên là các nút giao thông mà Baoma sẽ lần lượt đi qua. Nó đảm bảo luôn tồn tại và Baoma đi qua mỗi đường phố nhiều nhất 1 lần.
• ~m~ dòng tiếp theo mỗi dòng chứa 3 số ~u, v, w~ biểu diễn đường đi từ nút ~u~ đến ~v~ mất ~w~ phút.

Output

• Ghi ra một số duy nhất là thời gian tối thiểu để Ben hoàn thành công việc của mình.

Sample Input 1

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 1

21