#include <bits/stdc++.h>
#include "crocodile.h"
#define F first
#define S second
using namespace std;
vector<pair<int, int>> g[100007];
int times[100007];
bool if_exit[100007];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
priority_queue<pair<long long, int>> q;
int dist;
int v;
for (int i=0; i<m; i++) {g[r[i][0]].push_back({l[i], r[i][1]}); g[r[i][1]].push_back({l[i], r[i][0]});}
for (int i=0; i<n; i++) ranges::sort(g[i]);
for (int i=0; i<n; i++) times[i]=-1;
for (int i=0; i<k; i++) if_exit[p[i]]=1;
int c, m1, m2;
for (int i=0; i<n; i++){
c=0, m1=m2=1e9+7;
if (if_exit[i]) continue;
for (auto j:g[i]) {
if (if_exit[j.S]) {
c++; //ha ha ha
if (j.F<=m1) m2=m1, m1=j.F;
else if (j.F<=m2) m2=j.F;
}
}
//cout<<i<<' '<<c<<' '<<m1<<' '<<m2<<endl;
if (c>=2) q.push({-m2, i});
}
while (!q.empty()){
dist=-q.top().F, v=q.top().S; q.pop();
if (times[v]!=-1) continue;
times[v]=dist;
//cout<<v<<' '<<dist<<endl;
for (int i=1; i<g[v].size(); i++) if (!if_exit[g[v][i].S] && times[g[v][i].S]==-1) {q.push({-dist-g[v][i].F, g[v][i].S});}
}
return times[0];
}
