#include "crocodile.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int const INF = 1e9+7;
struct Edge{
int to;
int cost;
};
int const NMAX = 1e5;
vector <Edge> g[1 + NMAX];
int dist1[1 + NMAX];
int dist2[1 + NMAX];
int start[1 + NMAX];
int isQueue[1 + NMAX];
void computeBellman(int n, int k) {
for(int i = 1;i <= n;i++) {
dist1[i] = dist2[i] = INF;
}
queue <int> q;
for(int i = 1;i <= k;i++) {
dist1[start[i]] = dist2[start[i]] = 0;
q.push(start[i]);
isQueue[start[i]] = true;
}
while(!q.empty()) {
int from = q.front();
q.pop();
isQueue[from] = false;
//cerr << from << ' ' << dist1[from] << ' ' << dist2[from] << '\n';
for(int i = 0;i < g[from].size();i++) {
int to = g[from][i].to;
int newDist = dist2[from] + g[from][i].cost;
//cerr << " " << from << " - " << to << ' ' << dist1[to] << ' ' << dist2[to] << ' ' << newDist << '\n';
if(newDist < dist1[to]) {
dist2[to] = dist1[to];
dist1[to] = newDist;
if(!isQueue[to]) {
isQueue[to] = true;
q.push(to);
}
}else if(newDist < dist2[to]) {
dist2[to] = newDist;
if(!isQueue[to]) {
isQueue[to] = true;
q.push(to);
}
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i = 1;i <= M;i++) {
int a = R[i-1][0], b = R[i-1][1], c = L[i-1];
a++;
b++;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for(int i = 1;i <= K;i++) {
start[i] = P[i-1]+1;
}
computeBellman(N, K);
return dist2[1];
}
