만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

경솔한 동굴 탐험대

면접 대비

시간 제한1초메모리 제한1024 MB

요약
모닥불에서 퍼지는 연기가 도착하기 전에 각 역을 지나며, 시작 역에서 출구까지 가는 최단 시간을 구합니다.
난이도

보통10점 중 5점

유형
그래프, 최단 경로
정답자
아직 제출이 없습니다

문제

어느 날 동굴 탐험대가 아프리카의 동굴에 도전했다. 꽤 깊이 들어갔을 때 그들은 이상한 점을 알아챘다. 연기 냄새가 난 것이다. "설마 화산에 가까워진 건가?" 신입이 놀라 묻자 대장이 답했다. "아니다. 화산 근처에서는 유황 냄새가 난다." 대장이 다시 물었다. "누가 모닥불 끄는 일을 맡았지?" 모두 머뭇거리며 어깨를 으쓱했다. "자, 여러분, 우리는 갇혔다."

대장 앞에는 어려운 과제가 놓였다. 질식하지 않고 팀을 동굴 밖으로 이끄는 방법을 찾아야 한다. 동굴은 여러 개의 터널과 지점으로 이루어진다. 각 터널은 서로 다른 두 지점을 잇고 고유한 길이를 가진다. 대장은 동굴 지도를 가지고 있으며, 탐험대가 모닥불을 피운 지점과 출구의 위치를 안다.

연기는 매초 1미터씩 퍼진다. 연기가 찬 지점에 인접한 길이 kk의 터널은 kk초 뒤에 연기로 찬다. 그 터널 반대편의 지점도 함께 연기에 잠긴다. 탐험대가 연기가 있는 지점에 있으면 질식한다. 탐험대는 초속 1미터로 달린다. 터널은 양방향으로 통행할 수 있다. 처음에는 탐험대가 모닥불을 피운 지점에만 연기가 있다. 탐험대가 연기와 동시에 지점에 도착하면 질식한다. 출구 지점도 예외가 아니다. 탐험대가 지금 서 있는 지점에는 연기가 없다고 보장된다.

입력

첫 줄에 정수 NN, MM, KK가 주어진다. 각각 지점의 수, 터널의 수, 모닥불을 피운 지점의 수이며, 2≤N≤2×1052 \le N \le 2 \times 10^5, 0≤M≤2×1050 \le M \le 2 \times 10^5, 1≤K<N1 \le K < N이다. 둘째 줄에는 서로 다른 KK개의 정수 aia_i (1≤ai≤N1 \le a_i \le N)가 주어지며, 모닥불을 피운 지점의 번호이다. 이어서 MM줄에 걸쳐 세 정수 xix_i, yiy_i, lil_i가 주어진다. ii번째 터널이 지점 xix_i와 yiy_i를 잇고, 길이가 lil_i미터라는 뜻이다. 여기서 1≤xi,yi≤N1 \le x_i, y_i \le N, xi≠yix_i \ne y_i, 1≤li≤1091 \le l_i \le 10^9이다. 마지막 줄에는 두 정수 SS와 FF (1≤S,F≤N1 \le S, F \le N)가 주어진다. SS는 탐험대가 지금 있는 지점, FF는 출구의 지점이다.

출력

탐험대가 동굴에서 빠져나오는 데 걸리는 최소 시간(초)을 한 줄에 출력한다. 빠져나올 수 없다면 -1을 출력한다.

예제2

  1. 예제 1

    입력
    6 5 1
    6
    1 2 20
    2 3 2
    3 4 1
    2 5 1
    5 6 3
    4 1
    
    예상 출력
    23
    
  2. 예제 2

    입력
    6 6 2
    4 1
    4 1 1
    6 5 1
    2 4 1
    1 5 2
    5 6 2
    5 1 2
    3 6
    
    예상 출력
    -1