#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
const int maxN = 100000;
vector<pair<int, int>> AdjList[maxN];
int isExit[maxN];
int bestPlan[maxN][2];
int secondBest[maxN][2];
int dist[maxN];
void dijkstra(){
priority_queue<vector<int>> PQ;
for(int i = 0; i < n; ++i){
if(isExit[i]){
bestPlan[i][0] = secondBest[i][0] = 0;
bestPlan[i][1] = secondBest[i][1] = -1;
PQ.push({0, i, -1});
}
else{
bestPlan[i][0] = secondBest[i][0] = 1e9;
bestPlan[i][1] = secondBest[i][1] = -1;
}
}
//{-dist, nodo, padre};
while(!PQ.empty()){
vector<int> act = PQ.top(); PQ.pop();
int dist = -act[0];
int node = act[1];
int padre = act[2];
if(padre == secondBest[node][1] && dist == secondBest[node][0]){
//cout << node << " " << dist << endl;
for(pair<int, int> next: AdjList[node]){
int vecino = next.first;
int d = next.second + dist;
if(d < bestPlan[vecino][0]){
if(bestPlan[vecino][1] != -1){
secondBest[vecino][0] = bestPlan[vecino][0];
secondBest[vecino][1] = bestPlan[vecino][1];
bestPlan[vecino][0] = d;
bestPlan[vecino][1] = node;
PQ.push({-secondBest[vecino][0], vecino, secondBest[vecino][1]});
}else{
bestPlan[vecino][0] = d;
bestPlan[vecino][1] = node;
}
}else if(d < secondBest[vecino][0]){
secondBest[vecino][0] = d;
secondBest[vecino][1] = node;
PQ.push({-d, vecino, node});
}
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N;
m = M;
k = K;
int a, b, w;
for(int i = 0; i < M; ++i){
a = R[i][0];
b = R[i][1];
w = L[i];
AdjList[a].push_back({b, w});
AdjList[b].push_back({a, w});
}
memset(isExit, 0, sizeof(isExit));
for(int i = 0; i < k;++i) isExit[P[i]] = 1;
dijkstra();
return secondBest[0][0];
}
/*
int main(){
int N, M, K;
cin >> N >> M >> K;
int R[M][2];
int L[M];
int P[K];
for(int i = 0; i < M; ++i) cin >> R[i][0] >> R[i][1] >> L[i];
for(int i = 0; i < K; ++i) cin >> P[i];
cout << travel_plan(N, M, R, L, K, P);
return 0;
}
*/
