#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
int N, M;
vector<pii> G[101010];
set<pii> U;
LL F[101010], S[101010];
bool chk[101010];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
N=n, M=m;
for (int i=0; i<M; i++){
G[r[i][0]].push_back(pii(r[i][1], l[i]));
G[r[i][1]].push_back(pii(r[i][0], l[i]));
}
for (int i=0; i<k; i++) {
chk[p[i]] = true;
for (pii v : G[p[i]]){
if (!F[v.first] || F[v.first] > v.second) {
U.erase(pii(S[v.first], v.first));
S[v.first] = F[v.first], F[v.first] = v.second;
if (S[v.first]) U.insert(pii(S[v.first], v.first));
}
else if (!S[v.first] || S[v.first] > v.second) {
U.erase(pii(S[v.first], v.first));
S[v.first] = v.second;
U.insert(pii(S[v.first], v.first));
}
}
}
while(!U.empty()){
int u=U.begin()->second;
U.erase(U.begin());
chk[u] = true;
for (pii v : G[u]){
if (chk[v.first]) continue;
if (!F[v.first] || F[v.first] > v.second+S[u]) {
U.erase(pii(S[v.first], v.first));
S[v.first] = F[v.first], F[v.first] = v.second+S[u];
if (S[v.first]) U.insert(pii(S[v.first], v.first));
}
else if (!S[v.first] || S[v.first] > v.second+S[u]) {
U.erase(pii(S[v.first], v.first));
S[v.first] = v.second+S[u];
U.insert(pii(S[v.first], v.first));
}
}
}
return S[0];
}
