조조의 기차 여행

조조는 1초에 역 1에 있는 상태로 시작한다. 철도 정기권으로 기차를 타고 갈아타며 이동하다가, T1초 이상 T2초 이하인 어떤 시각에 다시 역 1에 있어야 한다.

역들과 역을 잇는 양방향 철도, 그리고 각 철도를 이동하는 데 걸리는 시간이 주어진다. 또한 모든 기차에 대해 경로의 첫 역을 출발하는 시각과 지나가는 역들의 순서가 주어진다. 기차는 경로에 있는 모든 역에 정차한다. 기차 경로에서 이웃한 두 역 사이의 이동 시간은 그 두 역을 잇는 철도의 시간과 같다.

비용으로 세는 것은 조조가 역에 머무른 시간뿐이다. 기차 안에서 이동하는 시간은 비용에 포함하지 않는다. 같은 시각에 같은 역에 두 기차가 있다면 추가 시간 없이 갈아탈 수 있다. 조건을 만족하도록 이동할 때, 조조가 역에서 보낸 총 시간의 최솟값을 구하라.

첫 줄에 정수 N, P, V, T1, T2가 주어진다. 각각 역의 수, 철도의 수, 기차의 수, 다시 역 1에 있어야 하는 시각 구간을 뜻한다. 제한은 2 <= N <= 1000, 1 <= V <= 1000, 1 <= T1 <= T2 <= 50000이다.

다음 P개 줄에는 철도 하나의 정보가 정수 S1, S2, T로 주어진다. 이는 S1에서 S2로 가거나 S2에서 S1로 가는 데 T초가 걸린다는 뜻이다. 제한은 1 <= T <= 600이다.

다음 V개 줄에는 기차 하나의 정보가 주어진다. 첫 번째 정수 T0는 그 기차가 경로의 첫 역을 출발하는 시각이다. 두 번째 정수 NS는 출발역과 종착역을 포함한 경로의 역 수이며, 1 <= NS <= 1000이다. 이어서 NS개의 정수가 주어지며, 이는 기차가 차례로 지나는 역 번호이다. 기차는 첫 역에서 마지막 역까지 이동하고, 마지막 역에서는 모든 승객이 내린다.

같은 줄에 있는 모든 수는 정확히 하나의 공백으로 구분된다.

조조가 역에서 보낸 총 시간의 최솟값을 정수 하나로 출력한다.