Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT135D - Di chuyển trong thành phố

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


Được gửi lên bởi:adm
Ngày:2013-03-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2017-10-22 08:40:35
CODE AC http://j.gs/9aG9
2014-08-17 11:17:43 Black Hole
thì ra mỗi thành phố Mister có thể đi đến nhiều lần
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.