#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned ll;
template<typename T> using vt = vector<T>;
using vi = vt<int>;
using vvi = vt<vi>;
using ii = pair<int, int>;
using vii = vt<ii>;
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define debug(x) cerr << #x << " -> " << x << '\n'
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int inf = 1e9 + 7;
const ll infll = 1e18 + 10;
using pll = pair<ll, ll>;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
vt<vii> a(n);
for(int i = 0; i < m; i++) {
a[r[i][0]].eb(l[i],r[i][1]);
a[r[i][1]].eb(l[i],r[i][0]);
}
vt<pll> d(n, {infll, infll});
priority_queue<pll, vt<pll>, greater<pll>> pq;
for(int i = 0; i < k; i++) {
d[p[i]] = {0,0};
pq.push({0, p[i]});
}
while(!pq.empty()) {
ll du = pq.top().F, u = pq.top().S;
pq.pop();
if(du != d[u].S || u == 0) continue;
for(ii v : a[u]) {
if(d[v.S].F > du + v.F) {
d[v.S] = mp(du + v.F, d[v.S].F);
if(d[v.S].S != infll) pq.push({d[v.S].S, v.S});
}
else if(d[v.S].S > du + v.F) pq.push({d[v.S].S = du + v.F, v.S});
}
}
return d[0].S;
}
