#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define S second
#define F first
#define LL long long
const int N1 = 2e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;
vector<pair<int,int>>adj[N1];
bool vis[N1];
LL mn1[N1],mn2[N1];
// LL dfs(int i){
// if(vis[i])
// return ans[i];
// vis[i] = 1;
// LL mn1 = LINF,mn2 = LINF;
// for(auto x:adj[i]){
// dfs(x.F);
// if(ans[x.F]+x.S<mn1)mn2 = mn1,mn1 = ans[x.F]+x.S;
// else if(ans[x.F]+x.S<mn2)mn2 = ans[x.F]+x.S;
// }
// ans1 = min(ans1,mn2);
// return ans[i] = min(ans[i],mn2);
// }
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = N;
for(int i=0;i<n;i++)
mn1[i] = mn2[i] = LINF;
for(int i=0;i<M;i++){
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
for(int i=0;i<K;i++)
mn1[P[i]] = mn2[P[i]] = 0;
priority_queue<pair<LL,int>>que;
for(int i=0;i<n;i++)
que.push({-mn2[i],i});
while(!que.empty()){
int u = que.top().S;
LL ans = -que.top().F;
que.pop();
if(vis[u])continue;
vis[u] = 1;
//printf("%d %lld\n",u,ans);
for(auto x:adj[u]){
int v = x.F;
//printf("%d %d %d\n",u,v,x.S);
if(ans+x.S<mn1[v])
mn2[v] = mn1[v],mn1[v] = ans+x.S;
else
if(ans+x.S<mn2[v])
mn2[v] = ans+x.S;
que.push({-mn2[v],v});
}
}
return mn2[0];
}
/*
#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;
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;
}
*/
