A group of friends live in towns of an undirected road network with n towns 0 .. n-1;
roads[i] = [u, v, km] (km >= 0). friends lists the home town of each friend (two friends may
share a town). They want to meet in one town so that the sum of everyone's shortest driving
distance is as small as possible.
Return [town, total]. If several towns tie, pick the smallest label. If no town can be reached by
every friend, return [-1, -1].
Examples
Input: n = 5, roads = [[0,1,2],[1,2,2],[2,3,2],[1,4,1]], friends = [0, 3, 4]
Output: [1, 7]
Explanation: meeting in town 1 costs 2 + 4 + 1 = 7; town 4 costs 8, towns 0 and 2 cost 9.
Input: n = 3, roads = [[0,1,1]], friends = [0, 2]
Output: [-1, -1]
Constraints
1 <= n <= 5000,0 <= len(roads) <= 10**4,1 <= len(friends) <= 20- Target
O(F * E log V)whereFis the number of distinct home towns.
Goals
- Run Dijkstra once from each friend's home
- Sum the distances per town and pick the best
- Handle towns that some friend cannot reach