Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

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

Khi Mister đang đi 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, tuy nhiên, những ai đã đi vào con đường trước khi Mister vào, vẫn có thể tiếp tục di chuyển và rời khỏi con đường này.

Luka vẫn cố gắng thực hiện công việc chở hàng của mình. Anh biết trước được lịch trình của Mister, và tính toán 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.

Hãy viết chương trình tính toán thời gian tối thiểu để Luka hoàn thành công việc của mình. Biết rằng Luka xuất phát chậm hơn Mister k phút.

Ví dụ, Mister đi vào 1 con đường vào lúc 10 phút và cần 5 phút để đi hết con đường, thì con đường này sẽ bị cấm trong các phút 10, 11, 12, 13, 14. Luka không thể đi vào được, tuy nhiên, anh có thể đi vào ở phút thứ 9 hoặc sớm hơn, ở phút 15 hoặc muộn hơn.

Input

Dòng đầu tiên gồm 2 số N, M (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10 000). Trong đó N là số nút giao thông, M là số con đường.

Dòng thứ 2 gồm 4 số A, B, K và G. (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000).

Thứ tự lần lượt là:
* Nút giao thông mà Luka xuất phát.
* Nút giao thông mà Luka muốn đến.
* Sự chênh lệch thời gian xuất phát của Luka so với Mister. Luka sẽ xuất phát tại nút A là k phút kể từ khi Mister xuất phát.
* Số nút giao thông trên đường đi của Mister.

Dòng thứ 3 chứa G số là các nút giao thông mà Mister sẽ đi qua. Dãy số này sẽ biểu diễn đường đi của Mister. Nó được đảm bảo luôn tồn tại và Mister đi qua mỗi đường phố nhiều nhất 1 lần.

M dòng tiếp theo, mỗi dòng gồm 3 số A, B, L, biểu diễn rằng để đi từ nút A tới nút B mất L phút.

Output

In ra thời gian tối thiểu để Luka có thể hoàn thành công việc giao hàng của mình.

Example

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

Ouput2:

40