#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int n, int m, int edges[][2], int w[], int k, int p[])
{
unordered_map<int,int> g[n];
unordered_map<int,int>index[n];
for(int i =0;i<m;i++){
g[edges[i][0]][edges[i][1]]=w[i];
g[edges[i][1]][edges[i][0]]=w[i];
index[edges[i][0]][edges[i][1]]=i;
index[edges[i][1]][edges[i][0]]=i;
}
bool ex[n];
bool rem[n];
bool vis[n];
fill(rem,rem+n,0);
fill(ex,ex+n,0);
fill(vis,vis+n,0);
set<tuple<int, int, int>> pq; // dist, destination, origin
unordered_map<int,int> mp;
for(int i = 0;i<k;i++){
vis[p[i]]=1;
ex[p[i]]=1;
}
for(int i = 0;i<k;i++){
for(pair<int,int>pa : g[p[i]]){
if(vis[pa.first]) continue;
pq.insert(make_tuple(pa.second, pa.first, p[i]));
}
}
while(!pq.empty()){
tuple<int, int, int> a = *(pq.begin());
pq.erase(pq.begin());
if(vis[get<1>(a)]){
continue;
}
if(rem[get<1>(a)]){
for(pair<int,int>p : g[get<1>(a)]){
if(vis[p.first]) continue;
if(mp[index[get<1>(a)][p.first]] != 0 && mp[index[get<1>(a)][p.first]] > get<0>(a) + p.second){
pq.erase(make_tuple(mp[index[get<1>(a)][p.first]], p.first, get<1>(a)));
}
pq.insert(make_tuple(get<0>(a) + p.second, p.first, get<1>(a)));
mp[index[get<1>(a)][p.first]] = get<0>(a) + p.second;
}
vis[get<1>(a)] = 1;
}
else{
// cout << "removing edge: " << get<1>(a) << " " << get<2>(a) << "\n";
g[get<1>(a)].erase(get<2>(a));
rem[get<1>(a)] = 1;
}
}
fill(vis,vis+n,0);
pq.insert(make_tuple(0, 0, -1));
vis[0] = 1;
while(!pq.empty()){
tuple<int, int, int> a = *(pq.begin());
pq.erase(pq.begin());
vis[get<1>(a)] = 1;
if(ex[get<1>(a)]) return get<0>(a);
for(pair<int,int>p : g[get<1>(a)]){
if(vis[p.first]) continue;
pq.insert(make_tuple(p.second + get<0>(a), p.first, get<1>(a)));
}
}
return -1;
}
