/**
* Author: Lưu Diệp Thành (Save Diệp Thành)
* Le Hong Phong High School for the Gifted (i2528)
**/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define ll long long
#define ushort unsigned short
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORN(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define endl '\n'
#define sz(x) (int)x.size()
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define ins insert
#define segleft (id<<1)
#define segright (id<<1|1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
const int MOD = 1e9+7;
const int INF = 1e9;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
vector<pair<int,int>> edge[n];
FOR(i, 0, m-1) {
edge[r[i][0]].pb({r[i][1], l[i]});
edge[r[i][1]].pb({r[i][0], l[i]});
}
vector<pair<int,int>> dist(n, {INF, INF});
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
FOR(i, 0, k-1) {
q.push({0, p[i]});
dist[p[i]] = {0,0};
}
while(!q.empty()) {
auto[du, u] = q.top(); q.pop();
if (du > dist[u].se or du = INF) continue;
for(auto[v,w] : edge[u]) {
if (dist[v].fi > du + w) {
dist[v].se = dist[v].fi;
dist[v].fi = du + w;
if (dist[v].se != INF) {
q.push({dist[v].se, v});
}
} else if (dist[v].se > du + w) {
dist[v].se = du + w;
q.push({dist[v].se, v});
}
}
}
return dist[0].se;
}
