Voronoi Diagram

문제

사진: 유클리드 좌표계에서 점 20개로 만든 Voronoi Diagram. 출처: Wikipedia

평면 위에 있는 크기 $n$ 의 점 집합을 생각하자. 이 점 집합의 Voronoi Diagram은 평면 위의 각 위치를 "어떤 점과 가장 가까운가"라는 기준으로 나눈 그림이다. 위 사진에서도 평면의 모든 위치가 자기와 가장 가까운 검은 점에 따라 색칠되어 있다. Voronoi Diagram을 $O(n \log n)$ 에 계산하는 알고리즘이 알려져 있지만, 어렵고 복잡하기로 악명이 높다.

어느 대회에서 Voronoi Diagram 문제를 풀지 못한 민규는 그 충격으로 매일을 술과 함께 보냈다. 어느 날 오후, 여느 때처럼 낮술을 하던 민규는 아주 천재적인 Voronoi Diagram 알고리즘을 발견했다! 민규는 논문을 쓰기 전에 대회에 이 알고리즘과 관련된 문제를 내서 만점자가 나오는 것을 막으려 한다.

민규의 Voronoi Diagram 알고리즘은 왜 천재적일까? 보통 Voronoi Diagram은 평면에서만 다루는데, 민규의 Voronoi Diagram은 더 일반화된 구조인 그래프에서 통하기 때문이다. 정점이 $N$ 개이고 가중치가 양수인 간선이 $M$ 개 있는 연결 그래프를 생각하자. 이 그래프에서 크기 $K$ 의 정점 집합이 주어졌을 때, 이 집합의 "Voronoi Diagram"은 그래프의 모든 간선 위의 위치를 "정점 집합에 있는 어떤 정점과 가장 가까운가"라는 기준으로 나눈 그림이다. 간선 위의 위치는 양 끝점만이 아니라 간선 내부의 모든 지점을 포함하고, 그런 위치와 정점 사이의 거리는 그래프를 따라 이동하는 최단 거리다. 거리가 같은 정점이 여러 개면 그중 번호가 가장 작은 정점을 기준으로 한다.

가중치 있는 그래프가 주어졌을 때, 정점 집합의 각 정점마다 "Voronoi Diagram"에서 그 정점에 배정된 간선 부분의 길이를 모두 더한 값을 출력해야 한다. 이 문제를 풀고 민규보다 먼저 논문을 써서 민규의 코를 납작하게 해주자!

입력

첫째 줄에 정점의 개수 $N$ 과 간선의 개수 $M$ 이 공백으로 구분되어 주어진다.

다음 $M$ 개 줄 중 $i$ 번째 줄에는 간선이 잇는 두 정점의 번호 $s_i$ , $e_i$ 와 간선의 가중치 $w_i$ 가 정수 세 개로, 공백으로 구분되어 주어진다. 같은 두 정점을 잇는 간선이 여러 개 있을 수 있고, 한 정점과 자기 자신을 잇는 간선도 있을 수 있다.

다음 줄에 정점 집합의 크기 $K$ 가 주어진다.

다음 줄에 $K$ 개의 서로 다른 정수 $a_i$ 가 오름차순으로, 공백으로 구분되어 주어진다. 정점 집합을 이루는 정점의 번호다.

입력으로 주어진 그래프는 연결 그래프임이 보장된다. 즉, 임의의 정점에서 임의의 정점으로 가는 경로가 존재한다.

출력

$K$ 개의 줄에 걸쳐 실수를 하나씩 출력한다. $i$ 번째 줄에는 $a_i$ 번 정점을 가장 가까운 정점으로 가지는 부분의 길이 합을 출력하라.

모든 값은 소수점 둘째 자리에서 반올림해서, 소수점 아래 한 자리까지 출력한다. 답은 언제나 $0.5$ 의 배수라서 반올림 때문에 값이 달라지는 경우는 없다. 실수 오차 관리에 초점을 맞춘 최근 ACM-ICPC World Finals의 경향에 맞춰, 출력에는 일체의 오차도 허용하지 않는다.

제한

$1 \le N, M \le 250\,000$
$1 \le s_i, e_i \le N$
$1 \le w_i \le 10^9$
$1 \le K \le N$
$1 \le a_i \le N$
주어진 그래프는 연결 그래프다.

힌트

예제를 그림으로 나타내면 다음과 같다.