#include "crocodile.h"
#include <vector>
#include <queue>
#include <iostream>
#include <set>
using namespace std;
typedef long long ll;
ll const INF = 1e15;
struct Edge{
int to;
ll cost;
};
int const NMAX = 1e5;
vector <Edge> g[1 + NMAX];
ll dist1[1 + NMAX];
ll dist2[1 + NMAX];
ll path1[1 + NMAX];
ll path2[1 + NMAX];
int start[1 + NMAX];
bool isQueue[1 + NMAX];
void computeBellman(int n, int k) {
for(int i = 1;i <= n;i++) {
dist1[i] = dist2[i] = INF;
isQueue[i] = false;
}
set <pair<pair<int,int>,int>> q;
for(int i = 1;i <= k;i++) {
dist1[start[i]] = dist2[start[i]] = 0;
q.insert({{0, 0}, start[i]});
isQueue[start[i]] = true;
}
while(!q.empty()) {
int from = q.begin()->second;
q.erase(q.begin());
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;
ll newDist = dist2[from] + g[from][i].cost;
//cerr << " " << from << " - " << to << ' ' << dist1[to] << ' ' << dist2[to] << ' ' << newDist << '\n';
if(path1[to] == from) {
dist1[to] = newDist;
} else {
if(newDist < dist1[to]) {
q.erase({{dist2[to], dist1[to]}, to});
dist2[to] = dist1[to];
path2[to] = path1[to];
dist1[to] = newDist;
path1[to] = from;
q.insert({{dist2[to], dist1[to]}, to});
}else if(newDist < dist2[to]) {
q.erase({{dist2[to], dist1[to]}, to});
dist2[to] = newDist;
path2[to] = from;
q.insert({{dist2[to], dist1[to]}, 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++;
cerr << a << ' ' << b << '\n';
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];
}
