드래곤볼 I
시간 제한2초메모리 제한512 MB
가중치가 있는 무방향 그래프와 일곱 개의 목표 도시가 주어질 때, 도시 1에서 출발해 일곱 곳을 모두 방문하는 최소 비용 경로를 구한다.
문제
행성 X에는 드래곤볼에 관한 전설이 하나 내려온다. 드래곤볼 일곱 개를 모으면 드래곤 신이 나타나 소원을 하나 들어준다고 한다.
어느 날, 그 전설이 사실일지도 모른다는 사실을 알게 된다. 벼룩시장에서 드래곤볼 레이더를 발견한 것이다. 이 레이더는 행성 X에 있는 일곱 개의 드래곤볼 위치를 보여준다. 오래된 소원 성취 전설이 사실인지 직접 확인하고 싶다.
행성 X에는 도시가 n개 있고, 1번부터 n번까지 번호가 붙어 있다. 지금은 1번 도시에 있다. 도시 사이를 이동할 때는 m개의 양방향 순간이동기를 이용할 수 있고, 각각을 원하는 만큼 여러 번 사용할 수 있다. i번째 순간이동기를 한 번 사용하는 데 ti코인이 들고, 이 순간이동기는 도시 ai와 bi 사이를 이동시켜 준다. 드래곤볼을 줍기 위해서는 레이더에 표시된, 드래곤볼이 있는 도시를 방문하면 된다. 여러 드래곤볼이 같은 도시에 있을 수도 있는데, 이때 그 도시를 방문하면 한꺼번에 모두 주워진다.
입력
첫째 줄에 도시의 수 n과 순간이동기의 수 m이 공백으로 구분되어 주어진다. (1 ≤ n, m ≤ 200,000)
다음 m개 줄에 각각 세 정수 ai, bi, ti가 공백으로 구분되어 주어진다. (1 ≤ ai, bi ≤ n, 0 ≤ ti ≤ 10,000) 이는 위에서 설명한 대로 순간이동기가 잇는 두 도시와 순간이동기를 사용하는 데 드는 비용을 나타낸다.
그다음 줄에 레이더에 나타난 일곱 개 드래곤볼의 도시 번호 일곱 개가 공백으로 구분되어 주어진다. 각 번호 c는 1 ≤ c ≤ n을 만족한다.
출력
레이더에 나타난 일곱 개의 드래곤볼을 모두 주우려면 필요한 최소 코인 수를 출력한다. 불가능하다면 -1을 출력한다.