#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f first
#define s second
#define pi pair<ll,ll>
#define vi vector<ll>
#define vpi vector<pi>
#define pb push_back
#define INF 1000000000000000
#define endl '\n'
//#define int ll
#define pii pair<pi,ll>
const int MAX = 1e5+1;
vpi g[MAX];
ll dis[MAX][2];
ll travel_plan(int n,int m, int R[][2], int L[],int k, int P[]){
ll a,b,c,from;
for(int i = 0; i < m; i++){
a = R[i][0];
b = R[i][1];
c = L[i];
g[a].pb({b,c});
g[b].pb({a,c});
}
priority_queue<pi, vector<pi>, greater<pi>>pq;
for(int i = 0; i < n; i++){
dis[i][0]=INF;
dis[i][1]=INF;
}
for(int i =0 ; i < k; i++){
dis[P[i]][0]=0;
dis[P[i]][1]=0;
pq.push({0,P[i]});
}
while(!pq.empty()){
b = pq.top().f;
from = pq.top().s;
pq.pop();
if(b!=dis[from][1]) {
continue;
}
for(pi i : g[from]){
int to = i.f;
int w= i.s;
if(dis[to][0]> b+w){
bool flag = false;
if(dis[to][0]!=INF ) flag = true;
dis[to][1] = dis[to][0];
dis[to][0] = b+w;
if(flag)pq.push({dis[to][1], to});
}
else if(dis[to][1]>b+w){
dis[to][1]=b+w;
pq.push({dis[to][1], to});
}
}
}
return dis[0][1];
}
/*
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1
3
4
1
3
*/
