악어의 지하 도시

고고학자 철수는 악어들이 사는 신비한 지하 도시를 탐험하던 중 위험을 느끼고 탈출하려 한다.

지하 도시는 $N$개의 방으로 이루어져 있으며, 방에는 $0$부터 $N-1$까지 번호가 붙어 있다. 서로 다른 두 방을 잇는 복도가 $M$개 있고, 각 복도는 통과하는 데 걸리는 시간이 정해져 있다. 같은 두 방을 잇는 복도는 많아야 하나이다. $N$개의 방 중 $K$개는 그 자리에서 곧바로 밖으로 나갈 수 있는 탈출방이다. 철수는 처음에 방 $0$(탈출방이 아님)에 있으며, 가능한 한 빨리 어느 탈출방으로든 도달하려 한다.

악어 문지기는 철수의 탈출을 막으려 한다. 문지기는 어느 한 순간에 복도 하나만 막을 수 있고, 새로운 복도를 막으면 이전에 막았던 복도는 다시 열린다. 구체적으로, 철수가 어떤 방을 떠나려 할 때 문지기는 그 방에 연결된 복도 중 하나를 막을 수 있다. 철수는 막히지 않은 복도 중 하나를 골라 이동한다. 일단 복도에 들어서면 이동을 마칠 때까지 그 복도는 막히지 않는다. 다른 방에 도착하면 문지기는 (방금 지나온 복도를 포함해) 다시 복도 하나를 막을 수 있으며, 이 과정이 반복된다.

철수는 탈출 계획을 미리 세워 둔다. 계획은 각 방에 도착했을 때 어떻게 행동할지를 미리 정해 둔 것이다. 방 $A$가 탈출방이면 즉시 탈출하므로 계획이 필요 없다. 탈출방이 아니라면 방 $A$에 대해 다음 중 하나가 정해져 있어야 한다.

방 $A$에서는 우선 방 $B$로 이동한다. 만약 그 복도가 막혀 있으면 방 $C$로 이동한다.
이 계획에서는 방 $A$에 절대 도달하지 않으므로, 아무 계획도 두지 않는다.

주의할 점은, 어떤 계획에서는 (예를 들어 철수가 사이클을 도는 경우) 문지기가 탈출을 영원히 불가능하게 만들 수도 있다는 것이다. 문지기가 어떤 전략을 쓰더라도 철수가 유한한 시간 안에 반드시 탈출함을 보장하는 계획을 좋은 계획이라 한다. 어떤 좋은 계획에서, 문지기가 어떻게 하든 그 시간이 지나면 철수가 반드시 탈출해 있음을 보장하는 최소 시간을 그 계획의 탈출 시간이라 한다.

입력으로 주어지는 값은 다음과 같다.

$N$ — 방의 수. 방은 $0$부터 $N-1$까지 번호가 붙어 있다.
$M$ — 복도의 수. 복도는 $0$부터 $M-1$까지 번호가 붙어 있다.
각 복도 $i$($0 \le i < M$)는 방 R[i][0]과 방 R[i][1]을 잇고, 통과에 L[i]($1 \le L[i] \le 10^9$)의 시간이 걸린다. 같은 두 방을 잇는 복도는 많아야 하나이다.
$K$ — 탈출방의 수($1 \le K < N$).
P[0], …, P[K-1] — 탈출방의 번호. 서로 다르며, 방 $0$은 포함되지 않는다.

가능한 모든 좋은 계획의 탈출 시간 중 최솟값 $T$를 구하라. 탈출방이 아닌 방에는 복도가 적어도 $2$개 연결되어 있다고 가정해도 좋다. 또한 모든 입력에는 $T \le 10^9$인 좋은 계획이 존재한다고 가정해도 좋다.

악어의 지하 도시

문제

입력

출력