2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8
Amin and Murad decided to create a "Minecraft" game server. They invited k guests to their grand opening ceremony. The invited guests live in different cities and will have a certain ping delay when connecting to the server (depending on the location). Amin and Murad, realizing the potential problem, decided to choose the most optimal location for the server.
There are n cities numbered from 1 to n and m two-way transmission channels between these cities. You can connect to the server only through these channels. Through these channels, you can create a connection between any two cities. However, no two cities can have more than one canal directly connecting them, and no city has canals connecting a city to itself. A delay time of
wi is also given for each channel. And so, the delay time for a connection from a city to a server is equal to the smallest sum of channel delays on the way from this city to a server among all possible paths.
Amin and Murad want to choose a city for the server so that the total connection delay of all guests is minimal during the connection. If the server is located in the city where some of the guests live, then the connection delay for this guest will be equal to 0.
If it is possible to select several cities with a minimum total delay, then Amin and Murad will choose the city with the lowest number. You need to find the city that Amin and Murad will choose and the total delay in connecting all guests to the server.
The first line contains three integers n, m, k - the number of cities, transmission channels and guests, respectively. The second line contains k different numbers
ci - the numbers of the cities where the guests live. Each of the following m lines contains three integers
wi. These numbers indicate a two-way link between the cities
vi with a delayed connection
Print two integers - the number of the city where the server will be located and the total delay in connecting all guests to this server.
- 1 ≤ n ≤
- 1 ≤ m ≤
- 1 ≤ k ≤ 100
- 1 ≤
- 1 ≤
This problem consists of 3 subtasks:
|1||w = 1||41 points|
|2||No additional restrictions||59 points|
5 6 3 1 2 5 1 2 10 1 4 3 2 4 2 2 5 8 3 4 5 3 5 3