#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9 + 20;
bool b[N], bl[N], exist[N];
int parent[N];
unordered_map<long long, long long> mp;
vector<vector<pair<long long, long long>>> v(N), adj(N);
queue<int> q;
void f(int x)
{
long long mn = INF, cnt = 0;
for (auto& it : adj[x])
{
if (!bl[it.first])
{
f(it.first);
}
if (exist[it.first])
{
cnt++;
if (mn >= it.second + mp[it.first])
{
mp[x] = min(mp[x], mn);
mn = it.second + mp[it.first];
}
else if (mp[x] >= it.second + mp[it.first])
{
mp[x] = it.second + mp[it.first];
}
}
}
if (cnt >= 2)
{
exist[x] = true;
}
else
{
mp[x] = INF;
}
bl[x] = true;
}
int travel_plan(int n, int m, int r[][2], int* l, int k, int* p)
{
for (int i = 0; i < n; i++)
{
b[i] = true;
bl[i] = false;
mp[i] = INF;
}
for (int i = 0; i < k; i++)
{
exist[p[i]] = true;
mp[p[i]] = 0;
bl[p[i]] = true;
}
for (int i = 0; i < m; i++)
{
v[r[i][0]].push_back({r[i][1], l[i]});
v[r[i][1]].push_back({r[i][0], l[i]});
}
q.push(0);
while (!q.empty())
{
int x = q.front();
q.pop();
b[x] = false;
for (auto& it : v[x])
{
if (b[it.first])
{
parent[it.first] = x;
adj[x].push_back(it);
if (!exist[it.first])
{
q.push(it.first);
}
}
}
}
f(0);
return mp[0];
}
