#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
const int mxn=1001;
vector<pair<int,int>>g[mxn];
bool ex[mxn];
int cn[mxn];
ll dp[mxn];
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
for(int i=0;i<m;i++){
g[r[i][0]].push_back({r[i][1],l[i]});
g[r[i][1]].push_back({r[i][0],l[i]});
}
for(int i=0;i<k;i++){
ex[p[i]]=1;
for(auto j:g[p[i]])cn[j.F]++;
}
for(int _=0;_<n;_++){
ll bt[]={-1,(ll)1e18};
for(int i=0;i<n;i++){
if(ex[i]||cn[i]<2)continue;
ll mn[]={(ll)1e18,(ll)1e18};
for(auto j:g[i]){
if(ex[j.F]){
ll val=j.S+dp[j.F];
if(val<=mn[0]){
mn[1]=mn[0];
mn[0]=val;
}
else if(val<mn[1])mn[1]=val;
}
}
if(mn[1]<bt[1])bt[0]=i,bt[1]=mn[1];
}
if(bt[0]!=-1){
ex[bt[0]]=1;
dp[bt[0]]=bt[1];
for(auto i:g[bt[0]])cn[i.F]++;
}
}
return dp[0];
}
