408918: GYM103380 D Lazy Santa

Santa has decided he wants to be lazy this year. Instead of delivering his presents himself, he has decided that he wants his elves to do it. Fortunately, Santa has an infinite number of elves at his disposal, and fortunately, $$$k$$$ elves volunteered to deliver presents to the $$$k$$$ houses that need presents to be delivered to.

There are $$$n + 1$$$ total locations in the world that Santa's elves can travel to, with location $$$0$$$ being the North Pole, where Santa and his elves currently reside. There are $$$k$$$ locations such that houses exist, and there are $$$m$$$ bidirectional pathways that connect two locations $$$m_u, m_v$$$ with a travel time of $$$m_c$$$ seconds. If two locations are not connected by any series of pathways, then trying to travel between them is infeasible. There may be multiple pathways between two houses, but it is guaranteed that all houses are reachable from location 0.

Given that each elf is assigned to one house and takes the most optimal route to and from their designated house, Santa is curious about two things. First, Santa wants to know the total travel time for all elves. Second, Santa wants to know the maximum travel time for any elf. Help Santa find the answer to his two questions!

The first line of the input will contain three space separated integers $$$n (1 \le n \le 10^4), k (1 \le k \le n), m (1 \le m \le 10^5)$$$, where $$$n + 1$$$ is the number of locations, $$$k$$$ is the number of houses, and $$$m$$$ is the number of pathways.

The next $$$k$$$ lines of input will each contain a number $$$k_i$$$ ($$$1 \leq k_i \leq n$$$) representing a house at location $$$k_i$$$. It is guaranteed all house locations are unique.

The next $$$m$$$ lines of input after that will each contain 3 space separated integers $$$m_u, m_v, m_c$$$, where $$$0 \le m_u, m_v \le n$$$, $$$m_u \neq m_v$$$, and $$$1 \le m_c \le 10^3$$$.

Output two space separated integers, the first being the total travel time for all the elves, and the second being the longest travel time of any elf.

5 3 6
3
5
4
2 3 5
4 2 2
0 4 2
2 1 6
1 5 9
5 1 4

50 28