#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int n, m, k;
bool spec[100001];
vector<pair<int, int>> g[100001], sp[100001];
array<int, 2> dist[100001];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N, m = M, k = K;
for(int i = 0;i < n;i++){
dist[i] = {(int)1e9, (int)1e9};
}
for(int i = 0;i < m;i++){
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
priority_queue<pair<int, int>> Q;
for(int i = 0;i < k;i++) {
Q.push(make_pair(0, P[i]));
dist[P[i]] = {0, 0};
}
while(!Q.empty()) {
pair<int, int> x = Q.top();
int w = Q.top().first,u = Q.top().second;
Q.pop();
w *= -1;
if(dist[u][1] < w) continue;
for(pair<int,int> v : g[u]) {
if(w + v.second < dist[v.first][0]) {
if(dist[v.first][0] < dist[v.first][1]) {
Q.push(make_pair(-dist[v.first][0], v.first));
}
dist[v.first][1] = dist[v.first][0];
dist[v.first][0] = x.first + v.second;
} else if(x.first + v.second < dist[v.first][1]) {
dist[v.first][1] = x.first + v.second;
Q.push(make_pair(-dist[v.first][1], v.first));
}
}
}
return dist[0][1];
}
