#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[]) {
vector<pair<int, int>> g[n];
for (int i = 0; i < m; i++) {
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
vector<vector<ll>> cost(n);
vector<int> vis(n, 0);
queue<int> q;
for (int i = 0; i < n; i++) {
if (g[i].size() == 1) {
vis[i] = 3;
cost[i].resize(3, 0);
q.push(i);
}
}
while (!q.empty()) {
auto u = q.front(); q.pop();
sort(cost[u].begin(), cost[u].end());
for (auto [v, w] : g[u]) {
if (vis[v] < 3) {
vis[v]++;
cost[v].push_back(cost[u][1] + w);
if(vis[v] == 3) q.push(v);
}
}
}
return cost[0][1];
}
