1. Problem Description:

Farmer John found a way to make the sweetest butter in Wisconsin: sugar. Put the sugar on a pasture and he knew that N cows would come and lick it, so that he could make super sweet butter that could sell well. Of course, he will pay extra for the cows. Farmer John is very cunning, just like Pavlov in the past. He knows that he can train these cows to go to a specific pasture when they hear the bell. He plans to put the sugar there and ring the bell in the afternoon so that he can milk at night. Farmer John knows that each cow is in his favorite pasture (a pasture does not necessarily have only one cow). Give the route of each cow between the pasture and the pasture, and find out the distance to which all the cows reach and the shortest pasture (he will put the sugar there). The data ensure that at least one pasture is connected to the pasture where all cattle are located.

Input format

The first row: three numbers: number of cows N, number of pastures P, and number of roads between pastures C. Line 2 to line N+1: the pasture number of 1 to N cows. Line N+2 to line N+C+1: each line has three numbers: connected pastures A and B, and the distance between the two pastures D. of course, the connection is two-way.

Output format

A total of one line, the output cow must walk the minimum distance and.

Data range

1 ≤ N ≤ 500，
2 ≤ P ≤ 800，
1 ≤ C ≤ 1450，
1 ≤ D ≤ 255

Input example:

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

Output example:

8
Source: https://www.acwing.com/problem/content/description/1129/

2. Train of thought analysis:

From the analysis of the problem, we can know that we need to find a starting point s in all pastures to minimize the sum of distances from the starting point s to other points. We can consider each pastures as the starting point and solve the sum of distances from this point to other points, To solve the sum of distances from each pasture as the starting point, finally take a min, which is the sum of the shortest distances from a point as the starting point to other points. Therefore, the essence of this problem is the shortest path problem of multi-source sink. The simplest is floyd algorithm, but the time complexity of floyd algorithm is O(n ^ 3), and the number of pastures P is 800 at most, Therefore, floyd cannot be used to solve the shortest distance between any two points. We can consider the following methods: ① simple version of Dijkstra algorithm ② heap optimized version of Dijkstra algorithm ③ spfa algorithm; These three algorithms solve the single source shortest path, so we also need to use a layer of circular enumeration to take a point as the starting point; For the simple version of Dijkstra algorithm, because each enumeration starts from a pasture, the time complexity is also O(n ^ 3), which is not desirable; For the heap optimized version of Dijkstra algorithm, the time complexity is O(nmlogn) = 1450 * 800 * log800=   11600000 * 10 = 10 ^ 7, barely passable; For spfa algorithm, the worst-case time complexity is O(nm) = 1450 * 800=   1160000 = 10 ^   6. In theory, spfa algorithm is the fastest, so we use spfa algorithm to solve it.

3. The code is as follows:

import collections
from typing import List


class Solution:
    # Because the time complexity of spfa is the smallest, the time complexity of other algorithms is very high
    def spfa(self, s: int, n: int, idx: List[int], g: List[dict]):
        q = collections.deque()
        q.append(s)
        INF = 10 ** 10
        dis = [INF] * (n + 1)
        dis[s] = 0
        vis = [0] * (n + 1)
        vis[s] = 1
        while q:
            p = q.popleft()
            vis[p] = 0
            for next in g[p].items():
                # After the current cur is used as the intermediate point, the distance between the remaining points is smaller, so it needs to be updated
                if dis[next[0]] > dis[p] + next[1]:
                    dis[next[0]] = dis[p] + next[1]
                    # Judge whether there are currently modified points in the queue. If not, add the current points
                    if vis[next[0]] == 0:
                        q.append(next[0])
                        # Sets the current tag as modified
                        vis[next[0]] = 1
        res = 0
        # Find the sum of the distances from the source point s to other points. If some points are found to be unreachable, INF is returned
        for i in range(len(idx)):
            if dis[idx[i]] == INF:
                res = INF
                break
            else:
                res += dis[idx[i]]
        return res

    def process(self):
        # Cows is the number of cows
        cows, n, m = map(int, input().split())
        idx = [0] * cows
        for i in range(cows):
            # Number of the i th cow
            idx[i] = int(input())
        g = [dict() for i in range(n + 1)]
        for i in range(m):
            x, y, z = map(int, input().split())
            # Because it is an undirected graph, we need to build two edges
            if y in g[x]:
                g[x][y] = min(g[x][y], z)
            else:
                g[x][y] = z
            if x in g[y]:
                g[y][x] = min(g[y][x], z)
            else:
                g[y][x] = z
        # Take each point as the starting point and the shortest distance to the other pastures
        INF = 10 ** 10
        res = INF
        # Note that the ranch number starts with 1
        for i in range(1, n + 1):
            t = self.spfa(i, n, idx, g)
            res = min(res, t)
        return res


if __name__ == "__main__":
    print(Solution().process())