#include <iostream>
#include <vector>
#include <set>
#include <ctime>
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
const int N = 1e6 + 5;
vector<pair<int,int>> lis[N];
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
ll Dis[n], vi[n] = {};
for (int i = 0; i < n; i++) Dis[i] = 1e18;
// Build graph
for (int i = 0; i < m; i++) {
int u = R[i][0], v = R[i][1];
lis[u].pb({v, L[i]});
lis[v].pb({u, L[i]});
}
set<vector<ll>> pq;
// Multi-source init
for (int i = 0; i < k; i++) {
Dis[P[i]] = 0;
pq.insert({0, P[i], P[i]});
vi[P[i]] = 1;
}
// Dijkstra variant
while (!pq.empty() && Dis[0] == 1e18) {
auto top = *pq.begin();
pq.erase(pq.begin());
int v = top[1];
ll d = top[0];
if (vi[v] != 1) {
vi[v]++;
continue;
}
Dis[v] = d;
vi[v]++;
for (auto &u : lis[v]) {
if (vi[u.fi] >= 2 || Dis[u.fi] != 1e18) continue;
pq.insert({Dis[v] + u.se, u.fi, v});
}
}
return Dis[0];
}
