#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
vector<pair<ll, ll>> dijkstra(vector<int> s, vector<vector<pair<ll, ll>>> &adj){
int n = adj.size();
vector<pair<ll, ll>> dist(n+1, {INF, INF});
vector<bool> vis(n+1, false);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
for(int i : s){
dist[i] = {0, 0};
pq.push({0, i});
}
while(!pq.empty()){
ll d_u = pq.top().first;
int u = pq.top().second;
pq.pop();
if(vis[u]){
continue;
}
vis[u] = true;
for(auto it : adj[u]){
int v = it.first;
ll w = it.second;
if(vis[v]) continue;
ll fetch = d_u+w;
if(dist[v].first > fetch){
swap(dist[v].first, fetch);
}
if(dist[v].second > fetch){
swap(dist[v].second, fetch);
}
if(dist[v].second < 1e18){
pq.push({dist[v].second, v});
}
}
}
return dist;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = N, m = M;
vector<vector<pair<ll, ll>>> adj(n+1);
for(int i = 1; i <= m; i++){
int u = R[i-1][0], v = R[i-1][1], w = L[i-1];
u++; v++;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> s;
for(int i = 1; i <= K; i++){
s.push_back(P[i-1]+1);
}
vector<pair<ll, ll>> dist = dijkstra(s, adj);
return dist[1].second;
}
