题目描述
农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。

当然，他将付出额外的费用在奶牛上。

农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。

他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。

给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

数据保证至少存在一个牧场和所有牛所在的牧场连通。

输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。

第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。

第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。

输出格式
共一行，输出奶牛必须行走的最小的距离和。

数据范围
1≤N≤500,2≤P≤800,1≤C≤1450,1≤D≤255

样例
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static int N = 510;
    static int M = 1460 * 2;
    static int P = 810;
    static int n;
    static int m;
    static int p;
    static int INF = 0x3f3f3f3f;
    static int[] id = new int[N];
    static int[] h = new int[P];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static boolean[] st = new boolean[P];
    static int[] dist = new int[P];
    static int idx = 0;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static int spfa(int start)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(dist, INF);
        dist[start] = 0;
        q.add(start);
        st[start] = true;

        while(!q.isEmpty())
        {
            int t = q.poll();
            st[t] = false;
            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];//获取点编号
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if(!st[j])
                    {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            int j = id[i];
            if(dist[j] == INF) return INF;//可能存在某个点与其他点不连通
            res += dist[j];
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        p = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0;i < n;i ++) id[i] = scan.nextInt();
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            add(a,b,c);
            add(b,a,c);
        }
        int res = INF;
        for(int i = 1;i <= p;i ++) res = Math.min(res, spfa(i));
        System.out.println(res);
    }
}