Voronoi Diagram

The picture shows a Voronoi diagram built from 20 points in the Euclidean plane. Source: Wikipedia

Consider a set of $n$ points in the plane. The Voronoi diagram of that set divides every position in the plane by the question "which point is the nearest one?". In the picture above, every position in the plane is colored according to the black point nearest to it. An algorithm that computes a Voronoi diagram in $O(n \log n)$ is known, but it is notorious for being difficult and complicated.

Mingyu failed to solve a Voronoi diagram problem at a contest, and the shock left him drinking every day. One afternoon, drinking as usual, he found a brilliant Voronoi diagram algorithm. Before he writes a paper about it, he wants to set a related contest problem so that nobody scores full marks.

Why is Mingyu's Voronoi diagram algorithm brilliant? A Voronoi diagram is normally defined only in the plane, but Mingyu's Voronoi diagram works on a graph, which is a more general structure. Consider a connected graph with $N$ vertices and $M$ edges of positive weight. Given a set of $K$ vertices of that graph, the "Voronoi diagram" of the set divides every position on the edges of the graph by the question "which vertex of the set is the nearest one?". A position on an edge is any point of the edge, the interior included, and the distance between such a position and a vertex is the shortest distance along the graph. When several vertices of the set sit at the same distance, the one with the smallest number is used.

Given a weighted graph, you have to print, for each vertex of the set, the total length of the edge parts assigned to that vertex in the "Voronoi diagram". Solve this problem, publish the paper before Mingyu does, and spoil his plan!

The first line contains the number of vertices $N$ and the number of edges $M$, separated by a space.

Each of the next $M$ lines contains three integers separated by spaces: the numbers $s_i$ and $e_i$ of the two vertices that the $i$-th edge joins, and the weight $w_i$ of that edge. Several edges may join the same pair of vertices, and an edge may join a vertex to itself.

The next line contains the size $K$ of the vertex set.

The next line contains $K$ distinct integers $a_i$ in increasing order, separated by spaces. They are the numbers of the vertices that form the set.

The graph given in the input is guaranteed to be connected. That is, a path exists from any vertex to any vertex.

Print one real number on each of $K$ lines. On the $i$-th line, print the total length of the parts whose nearest vertex of the set is vertex $a_i$.

Round every value at the second decimal place and print one digit after the decimal point. Every answer is a multiple of $0.5$, so the rounding never changes a value. Following the recent ACM-ICPC World Finals trend of focusing on floating point error control, no error at all is allowed in the output.

• $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$
• The given graph is connected.

The examples look like this.