레이팅 미적용지난주에 George 씨가 크로아티아를 방문했다. George 씨는 매우 중요한 인물이기 때문에, 그가 어떤 거리에 있는 동안 경찰은 그 거리로의 진입을 금지했다. 다만 George 씨보다 먼저 그 거리에 들어온 차량은 계속 운행할 수 있었다.
George 씨가 방문하는 동안 Luka는 트럭을 몰고 시내를 돌아다녔다. 그런데 일부 거리가 통제되는 바람에 배달을 제때 하지 못해 하마터면 일자리를 잃을 뻔했다. 이제 와서 늦었지만, 그는 배달을 더 잘 계획할 수 있었을지, 즉 George 씨가 방문하는 동안 배달에 필요한 최소 시간이 얼마였을지 궁금해하고 있다. 그는 George 씨가 지난 경로를 알고 있다.
도시는 교차로들과 이들을 잇는 양방향 거리로 모델링된다. 각 거리에 대해 Luka는 그 거리를 지나는 데 걸리는 시간을 알고 있다(George 씨도 같은 시간이 걸린다).
예를 들어 George 씨가 \(10\)번째 분에 어떤 거리를 지나가기 시작해 빠져나가는 데 \(5\)분이 걸린다면, 그 거리는 \(10\), \(11\), \(12\), \(13\), \(14\)번째 분 동안 통제된다. Luka는 \(9\)번째 분 이전이나 \(15\)번째 분 이후에 그 거리에 들어갈 수 있다.
Luka가 George 씨 도착 후 \(K\)분 뒤에 출발한다고 할 때, 배달에 필요한 최소 시간을 계산하는 프로그램을 작성하시오.
첫째 줄에 교차로의 수와 거리의 수인 두 정수 \(N\)과 \(M\) (\(2 \le N \le 1000\), \(2 \le M \le 10\,000\))이 주어진다. 교차로에는 \(1\)부터 \(N\)까지 번호가 붙어 있다.
둘째 줄에 네 정수 \(A\), \(B\), \(K\), \(G\) (\(1 \le A, B \le N\), \(0 \le K \le 1000\), \(0 \le G \le 1000\))가 주어진다. 순서대로 다음과 같다:
- Luka가 출발하는 교차로;
- Luka가 도착해야 하는 교차로;
- George 씨와 Luka의 출발 시각 차이(Luka는 George 씨가 경로를 시작한 지 정확히 \(K\)분 뒤에 교차로 \(A\)에서 출발한다);
- George 씨의 경로에 있는 교차로의 수.
셋째 줄에 정수 \(G\)개, 즉 George 씨가 방문할 교차로들의 번호가 주어진다. 인접한 두 정수의 쌍은 그가 지나갈 거리를 나타낸다. 그 거리는 반드시 존재하며, George 씨는 어떤 거리도 최대 한 번만 지난다.
다음 \(M\)개의 줄에는 세 정수 \(A\), \(B\), \(L\)이 주어진다. 교차로 \(A\)와 \(B\) 사이에 거리가 있고 지나는 데 \(L\)분이 걸린다는 뜻이다. \(L\)은 \(1\) 이상 \(1000\) 이하이다.
Luka가 배달에 필요한 최소 시간(분)을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 60점 |
6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15218 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 2340