#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int n, int m, int edges[][2], int weights[], int exitCount, int exits[]){
#define ll long long
ll incoming[n];
multiset<ll> dist[n];
memset(incoming, 0, sizeof(incoming));
for (ll x = 0; x < n; x++) dist[x].insert(INT_MAX/2),dist[x].insert(INT_MAX/2);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; //for those who have fulfilled the incoming >= 2 req
#define distUpdate(k, newval) dist[k].insert(newval); dist[k].erase(prev(dist[k].end()))
for (ll x = 0; x < exitCount; x++){
distUpdate(exits[x], 0);
distUpdate(exits[x], 0);
pq.push({0, exits[x]});
}
vector<pair<ll, ll>> adjList[n];
for (ll x = 0; x < m; x++){
adjList[edges[x][0]].push_back({edges[x][1], weights[x]});
adjList[edges[x][1]].push_back({edges[x][0], weights[x]});
}
while (!pq.empty()){
ll d = pq.top().first, node = pq.top().second;
pq.pop();
//cout << node << ' ' << d << '\n';
if (d > *prev(dist[node].end())) continue;
for (auto x : adjList[node]){
//cout << x.first << "upd\n";
ll prevSecond = *prev(dist[x.first].end());
if ( d + x.second < prevSecond){ //i.e. distUpdate was successful
incoming[x.first]++;
distUpdate(x.first, d + x.second);
if (incoming[x.first] >= 2) pq.push({*prev(dist[x.first].end()), x.first});
}
}
}
return *prev(dist[0].end());
}
