#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
typedef pair<ll, int> pii;
const int MAXN = 1e5 + 10;
const ll inf = 1e18;
int n, m, k, ext[MAXN];
ll g[MAXN], f[MAXN];
vector<pair<int, int> > adj[MAXN];
priority_queue<pii, vector<pii>, greater<pii> > q;
void dijkstra(){
for(int i = 1; i <= n; i++)
g[i] = f[i] = inf;
for(int i = 1; i <= k; i++){
int u = ext[i];
g[u] = f[u] = 0; q.push(mp(0, u));
}
while(!q.empty()){
pii p = q.top(); q.pop();
int u = p.se;
if(p.fi != f[u]) continue;
for(int i = 0; i < (int)adj[u].size(); i++){
int v = adj[u][i].fi, w = adj[u][i].se;
if(f[u] + w < g[v]){
if(chkmin(f[v], g[v]) && f[v] != inf)
q.push(mp(f[v], v));
g[v] = f[u] + w;
}else if(chkmin(f[v], f[u] + w))
q.push(mp(f[v], v));
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
// input
n = N, m = M, k = K;
for(int i = 0; i < m; i++){
int a = R[i][0] + 1, b = R[i][1] + 1, c = L[i];
adj[a].pb(mp(b, c));
adj[b].pb(mp(a, c));
}
for(int i = 1; i <= k; i++)
ext[i] = P[i - 1] + 1;
// dijkstra
dijkstra();
return (int)f[1];
}
