#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, ll> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
vector<pair<int,ll>>g[N];
int travel_plan(int NN, int MM, int R[][2], int L[], int KK, int P[]){
n=NN;
m=MM;
k=KK;
for(int i=0;i<m;i++){
// cout<<R[i][0]<<" "<<R[i][1]<<endl;
g[R[i][0]].push_back(make_pair(R[i][1],L[i]));
g[R[i][1]].push_back(make_pair(R[i][0],L[i]));
}
priority_queue<pii,vector<pii>,greater<pii>>q;
vector<ll>mn(n+1,INF),smn(n+1,INF);
// cout<<mn[0]<<" "<<smn[0]<<endl;
for(int i=0;i<k;i++){
q.push(make_pair(0,P[i]));
mn[P[i]]=smn[P[i]]=0;
}
while(!q.empty()){
int v=q.top().ss;
ll w=q.top().ff;
// cout<<v<<" "<<w<<endl;
// cout<<mn[v]<<" "<<smn[v]<<endl<<endl;
q.pop();
if(smn[v]==w){
for(pii x:g[v]){
int to=x.ff;
ll dist=x.ss;
// cout<<v<<" "<<to<<" "<<dist<<endl;
// cout<<mn[to]<<" "<<smn[v]<<endl;
// cout<<endl;
if(mn[to]>smn[v]+dist){
smn[to]=mn[to];
mn[to]=smn[v]+dist;
q.push(make_pair(smn[to],to));
}
else if(smn[to]>smn[v]+dist){
smn[to]=smn[v]+dist;
q.push(make_pair(smn[to],to));
}
}
}
}
return smn[0];
}
