#include "crocodile.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#define MAX_N 100005
#define MAX_M 1000005
#define ll long long
#define fi first
#define se second
using namespace std;
ll inf = 1000000000;
vector<pair<int,ll>>a[MAX_M];
int n,m,k,x,y,w;
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<m;i++){
x=R[i][0],y=R[i][1],w=L[i];
a[x].push_back({y,w});
a[y].push_back({x,w});
}
vector<ll>di(n,inf);
vector<int>vi1(n);
vector<int>vi(n);
priority_queue<pair<int,int>>o;
for (int i=0;i<k;i++){
o.push({0,P[i]});
vi1[P[i]]=1;
di[P[i]]=0;
}
while (o.size()){
auto hi=o.top();
o.pop();
int h=hi.se;
if (!vi1[h]){
vi1[h]=1;
continue;
}
if (vi[h])continue;
vi[h]=1;
di[h]=-hi.fi;
for (auto [i,w]:a[h]){
if (vi[i])continue;
o.push({-1*(di[h]+w),i});
}
}
return di[0];
}
