Homeless Jozo bought a monthly railway ticket so he could sleep in worm wagons and dream of a better life.

You are given a list of all stations and railways that connect them and their length (times it takes train to travel between to given stations). Railways are two-way and traveling in both ways last the same.

You are also given a list of all trains and the times of their departures and stations they are passing throw. Train stops at each station that it is passing throw.

At the beginning (in 1st second) Jozo is on the station number 1 and he has to return at that same station between T1 and T2 second. If there are two trains in the same time at the same station, he can jump from one train to another without losing time. You have to write a program that will choose a route such that Jozo can drive around and spend minimum total amount of time at the stations.

Input

First row of input file contains integers N, P, V, T1 i T2, 2 ≤ N ≤ 1000, 1 ≤ V ≤ 1000, 1 ≤ T1 ≤ T2 ≤ 50,000. N is number of stations, P is number of railways, V is number of trains, T1 and T2 are times explained in problem statement.

Each of next P rows contains data about one railway. It contains three integers S1, S2 and T. It means that journey from S1 to S2 (and vice versa) lasts T seconds, 1 ≤ T ≤ 600.

Each of next V rows contains data about one train. First number in that row is T0, time of departure from first station, second number is NS, 1 ≤ NS ≤ 1000, number of stations on train’s route (including starting and finishing station), next NS numbers are consecutively stations train passes through. Train goes from first to the last station where all passengers leave the train and train stays at the finishing station.

All numbers in the same row are separated by exactly one space character.

Output

First and only row of output file must contain time asked for in problem statement.

Sample

jozo.in 
 
4 4 3 30 35 
1 2 5 
2 3 2 
2 4 7 
3 4 3 
2 4 1 2 4 3 
14 4 3 4 2 3 
28 3 3 2 1 
 
jozo.out 
 
6

jozo.in 
 
4 6 5 80 100 
4 2 6 
2 1 16 
1 3 17 
1 4 19 
4 3 9 
3 2 10 
25 3 1 3 2 
25 3 1 2 4 
4 4 1 2 3 4 
52 4 4 2 1 4 
64 4 2 3 4 1 
 
jozo.out 
 
22

jozo.in 
 
4 6 7 80 100 
4 1 8 
1 3 7 
3 2 15 
1 2 2 
2 4 1 
4 3 3 
50 7 2 4 1 2 4 1 3 
25 10 4 3 1 2 4 3 1 2 4 1 
6 6 2 1 3 4 2 1 
11 5 4 2 3 1 4 
52 6 1 2 4 3 2 1 
23 5 3 2 4 1 2 
21 5 4 2 1 3 2 
 
jozo.out 
 
23