//#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1e5;
vector<pair<int, int>> dis;
vector<pair<int, int>> graph[maxN];
int par[maxN]; // i know this is not technically the parent, but
int fpath;
void dijkstra(int k, int P[]){
priority_queue<pair<int,int>> tv;
for(int i = 0; i < k; ++i) tv.push({0, P[i]});
while(!tv.empty()){
int node = tv.top().second;
int d = tv.top().first;
tv.pop();
if(d < dis[node].second) continue;
if(node = 0){
fpath = max(fpath, d);
continue;
}
for(pair<int,int> u : graph[node]){
if(d > dis[node].second && u.second != par[node]){
if(d + u.first > dis[node].first){
dis[u.second].second = dis[node].first;
dis[u.second].first = d + u.first;
par[u.second] = node;
}
else{
dis[u.second].second = d + u.first;
}
tv.push({d + u.first, u.second});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
memset(graph, 0, sizeof(graph));
for(int i = 0; i < M; i++){
graph[R[i][0]].push_back({-L[i],R[i][1]});
graph[R[i][1]].push_back({-L[i],R[i][0]});
}
int inf = -1e9;
dis = vector<pair<int,int>>(N,{inf,0});
dijkstra(K,P);
return -fpath;
}
