#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+45;
const ll inf = 1e18;
int n,m,k;
vector <pair<int,ll>> g[N];
bool ex[N];
ll dp1[N];
void dfstr(int x,int par){
vector <ll> svi;
for(auto f : g[x]){
int u = f.first;
if(u == par) continue;
ll w = f.second;
dfstr(u,x);
svi.push_back(dp1[u]+w);
}
if(svi.empty()) return;
assert(svi.size() >= 2);
sort(svi.begin(),svi.end());
dp1[x] = svi[1];
}
int zadrvo(){
dfstr(1,0);
return dp1[1];
}
struct Best{
ll p1 = inf, p2 = inf;
Best(){
p1 = p2 = inf;
}
Best(int p1, int p2): p1(p1), p2(p2){}
bool ok(){
return p1 != inf and p2 != inf;
}
void add(int num){
if (num <= p1)
p2 = p1, p1 = num;
else if (num <= p2)
p2 = num;
}
};
bool operator < (Best a, Best b){
return (a.p2 != b.p2) ? (a.p2 < b.p2) : (a.p1 < b.p1);
}
bool operator > (Best a, Best b){
return (a.p2 != b.p2) ? (a.p2 > b.p2) : (a.p1 > b.p1);
}
bool operator == (Best a, Best b){
return a.p1 == b.p1 and a.p2 == b.p2;
}
bool operator != (Best a, Best b){
return not (a == b);
}
Best f[N];
int travel_plan(int br,int M,int R[][2],int L[],int K,int P[]){
n = br;
m = M;
k = K;
for(int i = 0; i < m; i++){
g[R[i][0]+1].push_back({R[i][1]+1,L[i]});
g[R[i][1]+1].push_back({R[i][0]+1,L[i]});
}
for(int i = 0; i < k; i++){
ex[P[i]+1] = 1;
}
//return zadrvo();
priority_queue <pair<Best,int>,vector<pair<Best,int>>,greater<pair<Best,int>>> pq;
for(int i = 1; i <= n; i++){
if(ex[i]){
f[i] = {0,0};
pq.push({f[i],i});
}
else{
f[i] = Best();
}
}
while(!pq.empty()){
pair <Best,int> cur = pq.top();
pq.pop();
int u = cur.second;
Best sta = cur.first;
if(sta != f[u]) continue;
for(auto ff : g[u]){
int v = ff.first,cost = ff.second;
ll novav = sta.p2+cost;
Best dete = f[v];
dete.add(novav);
if(dete < f[v]){
f[v] = dete;
if(f[v].ok()) pq.push({f[v],v});
}
}
}
return f[1].p2;
}
