#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#include "crocodile.h"
using namespace std;
vector <pair<int,int > > adj[100000];
multiset <ll> IN[100000];
bool vis[100000];
int Ein[100000];
long long dis[100000];
struct cmp{
//pair<int,pair<int,int> > a, b ;
bool operator() (const pair<int,pair<ll,int> > &a, const pair<int,pair<ll,int> > &b) const {
if (a.se.se >= 2 && b.se.se >= 2)
return a.se.fi <= b.se.fi;
return (a.se.se >= 2);
}
};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for (int i = 0; i < M; i++) {
adj[ R[i][0] ].push_back( { L [i], R[i][1] } );
adj[ R[i][1] ].push_back( { L[i] , R[i][0] });
}
fill(dis,dis + 100000,2000000000000000);
set<pair<int,pair<ll,int> >,cmp > s;
for (int i = 0; i < K; i++)
s.insert ({P[i] , {0,2}}), Ein[P[i]] = 2,dis[P[i]] = 0;
// cout << s.size()<<'\n';
// exit(0);
while (!s.empty()) {
int v = s.begin()->first;
ll val = (s.begin()->se).fi;
int count = (s.begin()->se).se; // cout << v <<'\n';
if (count < 2) break;
s.erase(s.begin());
if (vis[v]) continue;
dis[v] = val;
vis[v] = 1;
for (auto i : adj[v]) {
int x = i.se;ll d = i.fi;
if (vis[x]) continue;
IN[x].insert(dis[v] + d);
s.erase ( { x, { dis[x],Ein[x] }});
Ein[x] ++;
if (IN[x].size() >= 2) {
auto it = IN[x].begin();
it++;
if (dis[x] > *it) {
dis[x] = *it;
}
}
s.insert ( { x, { dis[x],Ein[x] }});
}
}
return dis[0];
} /*
main() { int n,m,k;
cin >> n >> m >> k;
int R[m][2],L[m]; for(int i = 0; i < m ; i++ )cin >> R[i][0] >> R[i][1] >> L[i];
int P[k]; for (int i = 0 ; i < k ; i++) cin >> P[i];
travel_plan(n,m,R,L,k,P);
} */
/* 5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
*/
