#include "crocodile.h"
#include <bits/stdc++.h>
#define sup 1e9
#define MAX_N 50000
#define MAX_M 10000000
static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
#define pb push_back
#define sc second
#define ff first
#define INF 1e9+10;
vector<vector<pair<ll,ll>>> G;
ii dis[100010];
ll pos[100010];
int vis[100100];
int travel_plan(int N, int M,int R[][2], int L[], int K, int P[])
{
memset(vis,-1,sizeof vis);
G.assign(N,vector<pair<ll,ll>>());
for(int i=0;i<M;i++){
G[R[i][0]].pb(make_pair(R[i][1],L[i]));
G[R[i][1]].pb(make_pair(R[i][0],L[i]));
}
for(int i=0;i<N;i++){
dis[i].ff=INF;dis[i].sc=INF;
pos[i]=INF;
}
priority_queue<ii,vector<ii>,greater<ii>> pq;
for(int i=0;i<K;i++){
ll u=P[i];
pq.push(ii(0,u));
dis[u].ff=0;
dis[u].sc=0;
pos[u]=0;
}
while(!pq.empty()){
ii curr=pq.top();
pq.pop();
if(vis[curr.sc]==1)continue;
vis[curr.sc]=1;
//cout<<curr.ff<<" "<<curr.sc<<endl;
for(int i=0;i<G[curr.sc].size();i++){
ii v=G[curr.sc][i];
int dist=pos[curr.sc]+v.sc;
if(dist<=dis[v.ff].ff){
dis[v.ff].sc=dis[v.ff].ff;
dis[v.ff].ff=dist;
pos[v.ff]=dis[v.ff].sc;
pq.push(ii(pos[v.ff],v.ff));
}
else{
if(dist<dis[v.ff].sc){
dis[v.ff].sc=dist;
pos[v.ff]=dist;
pq.push(ii(dist,v.ff));
}
}
}
}
// cout<<dis[0].sc<<endl;
return dis[0].sc;
}/*
inline
void my_assert(int e) {if (!e) abort();}
void read_input()
{
int i;
my_assert(3==scanf("%d %d %d",&N,&M,&K));
for(i=0; i<M; i++)
my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
for(i=0; i<K; i++)
my_assert(1==scanf("%d",&P[i]));
my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = travel_plan(N,M,R,L,K,P);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
return 0;
}
*/
