#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int NMAX = 1e5;
const ll INF = 1e18;
struct PQElement {
int node;
ll d;
bool operator < (const PQElement &other) const {
return other.d < d;
}
};
vector<pair<int, int>> g[NMAX + 1];
int n, m;
vector<ll> d[NMAX + 1];
char is_end[NMAX + 1];
void Dijkstra() {
priority_queue<PQElement> pq;
for(int i = 1; i <= n; i++) {
if(is_end[i]) {
pq.push({i, 0});
pq.push({i, 0});
}
}
while(!pq.empty()) {
auto [node, curent_d] = pq.top();
pq.pop();
if(d[node].size() < 2) {
d[node].push_back(curent_d);
if(d[node].size() == 2) {
for(auto [next_node, edge_d] : g[node]) {
pq.push({next_node, curent_d + edge_d});
}
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N; m = M;
for(int i = 0; i < M; i++) {
int a = R[i][0]; a++;
int b = R[i][1]; b++;
int c = L[i];
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
for(int i = 0; i < K; i++) {
P[i]++;
is_end[P[i]] = 1;
}
Dijkstra();
return d[1][1];
}
