Like no Tomorrow

안녕하세요, 선생님. 아이리에요. 저희 방과후 디저트부가 학교에서 마지막 밴드 연습을 끝내고 이제 공연장으로 이동하려고 해요. 그런데 공연장으로 가는 길이 조금 복잡해졌어요…

학교에서 공연장으로 가려면 버스를 타야 하는데, 버스에는 일반 버스와 순환 버스가 존재하고, 각각 비용이 달라요. 물론 저희는 방과후 디저트부니까, 공연 전에 달콤한 디저트 카페에 들르는 건 필수겠죠? 하지만 저희가 가진 돈이 많지 않아서 최대한 아껴서 공연장까지 갈 수 있는 방법을 찾아야 해요.

상황 설명은 나츠 쨩이 가장 잘하니까, 다음은 나츠 쨩에게 설명을 부탁했어요.

정점이 $N$개, 가중치가 있는 간선이 $M$개인 방향 그래프 $G$에서 방과후 디저트부는 $1$번 정점인 학교에서 출발해 $N$번 정점인 공연장으로 향해야 한다. 공연장에 도착하기 전 반드시 디저트 카페를 하나 이상 방문해야 하고 그 경로 과정에서 총 비용이 최소가 되도록 해야 한다. 학교에서 공연장으로 갈 수 있는 방법은 항상 존재한다.

$1$번 정점인 학교와 $N$번 정점인 공연장을 제외한 나머지 정점 중 일부 $K$개의 정점은 디저트 카페 정점이다. 일반 버스, 순환 버스 둘 중 하나를 원하는 만큼 계속 타서 이동할 수 있다. 단, 버스를 통해 공연장에 방문하면 더 이상 다른 곳으로 이동하지 않는다. 버스에는 아래와 같이 두 종류가 있다.

• 일반 버스

  • 서로 다른 두 장소 사이를 이동할 때 이동한 거리만큼 요금을 지불해야한다.
  • 이동한 거리는 이동한 간선들의 가중치 합이다.

• 순환 버스

  • 서로 왕복이 가능한 정점들 사이에서만 운행한다. 여기서 두 정점 $u, v$가 서로 왕복 가능하다는 것은 $u$에서 $v$로 가는 방향 경로와 $v$에서 $u$로 가는 방향 경로가 모두 존재함을 의미한다.
  • 순환 버스 요금은 버스를 탄 정점에서 처음 타는 간선의 가중치가 된다.
  • 한 정점에서 순환 버스를 타고 다른 한 정점을 이동할 때 두 정점들을 제외하고 방문한 것으로 처리하지 않는다.

… 라고 나츠 쨩이 쓰라고 하네요.

선생님. 저희들을 위해 공연장까지 가는 데 드는 최소 비용을 찾아주세요.

두 번째 줄에 디저트 카페가 있는 정점 번호가 공백으로 구분되어 주어진다. 이 정점 번호는 $2$이상 $N - 1$이하 이다.

세 번째 줄부터 $M$의 줄에 걸쳐 간선의 정보가 주어진다. 그 중 $i$번째 줄에는 $u_i$, $v_i$, $c_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점을 잇는 간선이 존재하며, 그 간선의 가중치는 $c_i$라는 의미이다. $(1 \le u, v \le N$; $u \neq v$; $1 \le c_i \le 1\,000)$ 서로 다른 두 간선 $i, j$에 대해 $(u_i, v_i) \neq (u_j, v_j)$인 경우만 주어진다.

시간 제한

2000 ms

메모리 제한

1024 MB

체커

CUSTOM