#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int NN=1e5+10;
vector<pair<ll,int>> adj[NN];
ll d[NN],sd[NN],pd[NN],psd[NN];
ll sew[NN];
//second edge weight to go to i
bool vs[NN],out[NN];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<N;i++) d[i]=sd[i]=LLONG_MAX;
for(int i=0;i<M;i++){
int u=R[i][0],v=R[i][1];
adj[u].push_back({v,L[i]});
adj[v].push_back({u,L[i]});
}
//multiple source shortest path
for(int i=0;i<K;i++) d[P[i]]=0,q.push({0,P[i]}),out[P[i]]=true;
while(!q.empty()){
int u=q.top().second;
q.pop();
for(auto [v,w]:adj[u]){
if(d[u]+w<d[v]){
d[v]=d[u]+w;
pd[v]=u;
q.push({d[v],v});
}
}
}
// for(int i=0;i<N;i++) cout<<d[i] <<" ";
// cout<<"\n";
/*for(int i=0;i<M;i++){
int u=R[i][0],v=R[i][1];
ll w=L[i];
//u->v
if(d[u]+w<=sd[v]){
if(pd[v]!=u){
sd[v]=d[u]+w;
psd[v]=u,sew[v]=w;
}
}
//v->u
if(d[v]+w<=sd[u]){
if(pd[u]!=v){
sd[u]=d[v]+w;
psd[u]=v,sew[u]=w;
}
}
}*/
int now=0;
ll ans=0;
for(int i=0;i<N;i++) vs[i]=false;
while(!out[now]){
ll mn=LLONG_MAX,wi;
int nxt;
//cout<<now <<" " <<ans <<" ";
vs[now]=true;
for(auto [v,w]:adj[now]){
if(vs[v]) continue;
if(v==pd[now]) continue;
if(mn>w+d[v]){
mn=w+d[v];
nxt=v;
wi=w;
}
}
now=nxt;
ans+=wi;
}
return ans;
}
