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 ui, vi, wi. These numbers indicate a two-way link between the cities ui and vi with a delayed connection wi.


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.


  • 1n104
  • 1m4∙104
  • 1k100
  • 1ci, ui, vin
  • 1wi104


This problem consists of 3 subtasks:

0Example0 points
1w = 141 points
2No additional restrictions59 points
Time limit 1 second
Memory limit 128 MiB
Input example #1
5 6 3
1 2 5
1 2 10
1 4 3
2 4 2
2 5 8
3 4 5
3 5 3
Output example #1
2 13
Source 2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8