Olympiad in Alchemy (decision through graphs)

Moscow Olympiad VIII. Absentee round 2005-2006 school year.

The task

In the state of alchemists there are N settlements numbered from 1 to N, and M roads. Localities are of two types: villages and cities. In addition, there is one capital in the state (it can be located both in the city and in the village). Each road connects two settlements, and it takes T _j minutes to drive through it. In the capital, it was decided to hold the 1st state command competition in alchemy. To do this, messengers were sent to all cities from the capital (one messenger per city) with information about the Olympiad.

Write a program that considers in what order and after what time each of the messengers will get to their city. It is believed that the messenger does not sleep during the journey and never lingers.

Input

In the input file, first recorded 3 numbers: N, M, K - the number of settlements, the number of roads and the number of cities (2 <= N <= 1000, 1 <= M <= 10000, 1 <= K <= M). Next is the number of the capital С (1 <= С <= M). The following K numbers give the numbers of cities. Then follow M triples of numbers Si, Ei, Ti, describing the roads: Si and Ei are the numbers of settlements that the road connects, and Ti, is the time to travel on it (1 <= Ti <= 100).

It is guaranteed that each city from the capital can be reached by road (possibly through other localities).

Conclusion

Output in the output file K pairs of numbers: for each city its number should be displayed and the minimum time after which the messenger can appear in it (time is measured in minutes since the messengers left the capital). Pairs in the output file must be ordered by the time of arrival of the messenger.

  Input Example Output Example
 5 4 5 1 1 0	
 12 3 4 5 2 1	
 1 2 1 3 11	
 2 3 10 4 111	
 3 4 100 5 211	
 4 5 100		


 5 5 3 1 5 1	
 2 4 5 2 1	
 2 1 1 4 101	
 2 3 10		
 3 4 100		
 4 5 100		
 1 5 1		

Decision

We take settlements for the top of the graph, and the roads between them - for the weighted edges. Formally, we need to find the shortest paths from a given vertex of the graph (capital) to all other vertices.

The solution to this problem uses one of the standard algorithms on graphs: Dijkstra's algorithm. For each nicked point with the help of Dijkstra's algorithm, we find the smallest time for which the messenger can reach it. After that, it remains to select settlements that are cities, and sort them by non-decreasing computed time.

Formal description

  Olymp ()
 1. Read the list of graph edges and their weight from the file.
 2. Create an adjacency matrix for the graph.
 3. According to Dijkstra's algorithms, find the shortest distances from the top;
    the capital to all the other vertices of the graph (perform paragraphs 3.1-3.4):
    3.1.  Initialize the distance to the vertices to infinity, 
         all tags about finding the shortest path to zeros.
    3.2.  Set the distance to the starting vertex to be 0.
    3.3.  Until the shortest paths are found for all vertices, repeat 
         pp  3.3.1-3.3.3:
         3.3.1.  Find the top, the shortest path for which is not found,
                with a minimum distance.
         3.3.2.  Assume that the shortest path for this vertex is found.
         3.3.3.  Update the distance to the incident to the current vertices.
 4. Sort the vertices by increasing the distance to them.
 5. Select the first vertex.
 6. Until all vertices are processed, repeat paragraphs.  6.1.-6.2:
    6.1.  If the current vertex is a city, then output its number
         and the distance about her.
    6.2.  Go to the next vertex of the graph.

Graph task for the first test. (Green backgrounds have tops-cities, the red border is the capital, the minimum distances to the peak are shown in brackets)

Graph task for the second test. (Green backgrounds have tops-cities, the red border is the capital, the minimum distances to the peak are shown in brackets)