#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include "crocodile.h"
using namespace std;
const int INFINI = (1000 * 1000 * 1000);
const int MAX_NOEUDS = (100 * 1000);
vector <pair <int, int>> Voisins[MAX_NOEUDS];
pair <int, int> DistMin[MAX_NOEUDS];
bool Vu[MAX_NOEUDS];
priority_queue <pair <int, int>> Dijkstra;
void Push() {
int noeud = Dijkstra.top().second;
int dist = DistMin[noeud].second;
Dijkstra.pop();
if (Vu[noeud])
return;
Vu[noeud] = true;
for (pair <int, int> dest : Voisins[noeud])
{
if (!Vu[dest.first])
{
int nouvDist = dist + dest.second;
if (nouvDist < DistMin[dest.first].first)
{
DistMin[dest.first].second = DistMin[dest.first].first;
DistMin[dest.first].first = nouvDist;
}
else if (nouvDist < DistMin[dest.first].second)
DistMin[dest.first].second = nouvDist;
if (DistMin[dest.first].second < INFINI)
Dijkstra.push({- nouvDist, dest.first});
}
}
return;
}
int travel_plan(int nbNoeuds, int nbAretes, int Aretes[][2], int Longueur[], int nbSorties, int Sorties[]) {
for (int i = 0; i < nbNoeuds; i ++)
{
DistMin[i].first = DistMin[i].second = INFINI;
}
for (int i = 0; i < nbAretes; i ++)
{
Voisins[Aretes[i][0]].push_back({Aretes[i][1], Longueur[i]});
Voisins[Aretes[i][1]].push_back({Aretes[i][0], Longueur[i]});
}
for (int i = 0; i < nbSorties; i ++)
{
DistMin[Sorties[i]].first = DistMin[Sorties[i]].second = 0;
Dijkstra.push({0, Sorties[i]});
}
while (!Dijkstra.empty())
{
Push();
}
return DistMin[0].second;
}
