GEORGE - George


Last week Mister George visited Croatia. Since Mister George is a very important person, while he was in a street, the police disallowed entry to that street, but vehicles that entered the street before Mister George could continue driving.

While Mister George was visiting, Luka drove his truck around town. But because of some of the streets being closed off, he couldn't make his delivery in time and almost lost his job. Although it is late now, he is wondering how he could have planned his delivery better i.e. what would have been the least time needed to make his delivery while Mister George was visiting. He knows the route mister George took.

The city is modeled with intersections and two-way streets connecting them. For each street, Luka knows how much time he needs to traverse it (mister George needs he same amount of time).

For example, if Mister George starts traversing a street during minute 10 and needs 5 minutes to exit it, this street will be blocked during minutes 10, 11, 12, 13 and 14. Luka can enter the street during minutes 9 and earlier, or 15 and later.

Write a program that calculates the least amount of time Luka needs to make his delivery, if he starts driving K minutes after the arrival of Mister George.

Input

The first line contains two integers N and M (2 <= N <= 1000, 2 <= M <= 10 000), the number of intersections and the number of streets. The intersections are numbered 1 to N. The second line contains four integers A, B, K and G (1 <= A, B <= N, 0 <= K <= 1000, 0 <= G <= 1000). These are, in order:

  • The intersection where Luka starts;
  • The intersection Luka must get to;
  • The difference in starting times between mister George and Luka (Luka starts at intersection A exactly K minutes after mister George starts his route);
  • The number of intersections on Mister George's route.
The third line contains G integers, the labels of intersections mister George will visit. Every pair of adjacent integers denotes a street he will traverse. That street will exist and Mister George will traverse every street at most once. Each of the following M lines contains three integers A, B and L, meaning that there is a street between intersection A and B, and it takes L minutes to traverse. L will be between 1 and 1000.

Output

Output the least amount of time (in minutes) Luka needs to make his delivery.

Example

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

Output:
21

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

Output:
40

Croatian Open Competition in Informatics (COCI) - 2007/2008 Contest #6

hide comments
nadstratosfer: 2018-05-21 16:05:53

Good problem, but would be a nightmare to get right without the comments. Some are confusing though, so summing up:
- Second line of input represents Mr. George's route; he travels between every pair of intersections once and in the given order
- Luca's route does not depend on road closures (but time to travel it does!)
- G >= 2

kmkhan_014: 2018-05-20 21:45:00

I confirm that each street in george's path is traversed once by him.

Thotsaphon Thanatipanonda: 2017-11-10 09:54:33

All of these statements are true
- That street will exist and Mister George will traverse every street at most once
- The answer path is not necessary equal to shortest path without delay

sharif ullah: 2017-09-28 07:31:33

WA??
1.pay attention on the calculation of blocking time !!!!! of the street

pranav0123: 2017-06-07 22:16:18

Question is not clear. Assume that George takes the path given by Djikstra's algorithm even if it takes more time due to delays caused by blocked roads to solve the problem.

gboduljak: 2017-04-02 23:58:27

hint: take care when calculating George's path, not all George's input intersections are connected, cost me so much WA

although, good problem :)

Last edit: 2017-04-02 23:58:50
Saksham : 2016-03-09 10:59:17

Good problem

hodobox: 2015-12-21 02:19:26

I can also confirm each street is traversed at most once. Replaced vector to 1 element and still got AC.

hodobox: 2015-12-21 02:15:00

In the first case, Luka will have to wait 1 minute while George is going from 3 to 2 (she gets to intersection 2 22 minutes after George starts, which means he will have finished 7 minutes of the 8 minute journey from 3 to 2), so the answer is 21 (20 shortest path + 1 minute waiting)

Deepak Gupta: 2014-12-12 18:13:44

The street is closed both ways.


Added by:Andrés Mejía-Posada
Date:2009-01-25
Time limit:0.172s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Croatian Open Competition in Informatics (COCI) - 2007/2008 Contest #6