#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int n, int m, int kr[][2], int dl[], int k, int wyjscia[]){
//cout << "lets do this" << endl;
//cout << n << ' ' << m << ' ' << k << endl;
vector<pair<int, long long>> graf[n + 1];
for(int i = 0; i < m; i++){
graf[kr[i][0]].push_back({kr[i][1], dl[i]});
graf[kr[i][1]].push_back({kr[i][0], dl[i]});
}
priority_queue<pair<long long, int>> Q;
int sumy[n];
bool odw[n];
long long wyn[n];
long long minn[n];
for(int i = 0; i < n; i++){
sumy[i] = 0;
wyn[i] = LLONG_MAX;
odw[i] = 0;
}
for(int i = 0; i < k; i++){
Q.push({0, wyjscia[i]});
sumy[wyjscia[i]] = 2;
wyn[wyjscia[i]] = 0;
}
//cout << "cos nie pyklo" << endl;
while(!(Q.empty())){
int v = Q.top().second;
long long odl = -Q.top().first;
Q.pop();
if(odw[v]){continue;}
odw[v] = 1;
// cout << "Jestem w " << v << " z wynikiem " << wyn[v] << endl;
for(auto i:graf[v]){
if(odw[i.first]){continue;}
if(!sumy[i.first]){
minn[i.first] = wyn[v] + i.second;
}
else{
if(wyn[v] + i.second <= minn[i.first]){
wyn[i.first] = minn[i.first];
minn[i.first] = wyn[v] + i.second;
Q.push({-wyn[i.first], i.first});
}
else if(wyn[v] + i.second < wyn[i.first]){
wyn[i.first] = wyn[v] + i.second;
Q.push({-wyn[i.first], i.first});
}
}
sumy[i.first]++;
}
}
return wyn[0];
}
