#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define all(x) begin(x), end(x)
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<vector<pair<int, ll>>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].pb({R[i][1], L[i]});
adj[R[i][1]].pb({R[i][0], L[i]});
}
vector<pair<ll, ll>> dist(N, {LLONG_MAX, LLONG_MAX});
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
for (int i = 0; i < K; i++) {
dist[P[i]].first = 0;
pq.push({0, P[i]});
}
while (!pq.empty()) {
auto curr = pq.top(); pq.pop();
if (curr.first >= dist[curr.second].second) {
continue;
}
if (curr.first < dist[curr.second].first) {
dist[curr.second].second = dist[curr.second].first;
dist[curr.second].first = curr.first;
}
else {
dist[curr.second].second = curr.first;
}
if (dist[curr.second].second != LLONG_MAX) {
for (auto x : adj[curr.second]) {
pq.push({dist[curr.second].second + x.second, x.first});
}
}
}
return dist[0].second;
}
//int main() {
// FAST_IO;
//freopen("fcolor.in", "r", stdin);
//freopen("fcolor.out", "w", stdout);
//TEST_CASES;
//solve(); cout << endl;
/*int a; cin >> a;
for (int i = 1; i <= a; i++){
cout << "Case #" << i << ": ";
solve();
cout << endl;
}*/
//}
