#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[2], 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<ll> dist(N, LLONG_MAX);
vector<bool> visited(N, false);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
for (int i = 0; i < K; i++) {
visited[P[i]] = true;
pq.push({0, P[i]});
}
while (!pq.empty()) {
auto curr = pq.top(); pq.pop();
if (curr.first >= dist[curr.second]) {
continue;
}
dist[curr.second] = curr.first;
for (auto x : adj[curr.second]) {
if (visited[x.first]) {
pq.push({curr.second + x.second, x.first});
}
else {
visited[x.first] = true;
}
}
}
return dist[0];
}
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;
}*/
}
