#include "crocodile.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
int n, m;
vector < pair < int, int > > g[maxn];
int k, isexit[maxn];
int dist[maxn];
int used[maxn];
void dijkstra()
{
priority_queue < pair < int, int > > q;
for (int i = 0; i < n; ++ i)
{
if(!isexit[i])dist[i] = 1e9;
else
{
q.push({0, i});
used[i] = 1;
dist[i] = 0;
}
}
while(!q.empty())
{
int w = q.top().second;
int d = -q.top().first;
q.pop();
if(used[w] >= 2)continue;
used[w] ++;
if(used[w] == 1)continue;
dist[w] = d;
for (auto &[nb, cost]: g[w])
{
if(dist[nb] > dist[w] + cost)
{
q.push({-dist[w] - cost, nb});
}
}
}
}
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)
{
int from, to, cost;
from = R[i][0];
to = R[i][1];
cost = L[i];
g[from].pb({to, cost});
g[to].pb({from, cost});
}
k = K;
for (int i = 0;i < k; ++ i)
isexit[P[i]] = 1;
dijkstra();
return dist[0];
}
