import heapq as h
class Solution:
    def Length(self , nn , nm , path , nnn ):
        # write code here
        g=[[] for _ in range(nnn+1)]
        for x,y,val in path:
            g[x].append((y,val))
            g[y].append((x,val))
        nmq={}
        for x in nm:
            nmq[x]=1
        res=1e13
        vis=[0]*(nnn+1)
        q=[]
        for x in nn:
            q.append((0,x))
            vis[x]=1
        while q:
            val,now=h.heappop(q)
            for nex,co in g[now]:
                if vis[nex]==1:
                    continue
                vis[nex]=1
                if nex in nmq:
                    res=min(res,val+co)
                h.heappush(q,(val+co,nex))
        return res if res!=1e13 else -1

class Solution {
public:
    /**
     * 
     * @param niuniu int整型vector 牛牛占领的p个星球的编号
     * @param niumei int整型vector 牛妹占领的q个星球的编号
     * @param path int整型vector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int整型 星球个数n
     * @return int整型
     */
    int Length(vector<int>& nn, vector<int>& nm, vector<vector<int> >& path, int nnn) {
        // write code here
        vector<pair<int,int>> g[100005];
        for (auto &ll : path){
            int x=ll[0];
            int y=ll[1];
            int val=ll[2];
            g[x].push_back(make_pair (y,val));
            g[y].push_back(make_pair (x,val));
            
        }
        int res=2147483647;
        int vis[100005];
        for( int i=0;i<100005;i++){
            vis[i]=0;
        }
        map<int,int> nmq;
        for (auto &x : nm){
            nmq[x]=1;
        }
        priority_queue<pair<int, int>>  q;
        for (auto &x : nn){
            q.push(make_pair(0,x));
            vis[x]=1;
        }
        while (!q.empty()){
            pair<int,int> now_ = q.top();
            q.pop();
            int val=-now_.first;
            int now=now_.second;
            for (auto &ll : g[now]){
                int nex=ll.first;
                int co=ll.second;
                if (vis[nex]==1) continue;
                if (nmq.find(nex)!=nmq.end()) res=min(res,val+co);
                q.push(make_pair(-val-co,nex));
                vis[nex]=1;
            }
        }
        if (res==2147483647) return -1;
        return res;
    }
};