#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e5;
ll inf = 1e12;
vector <pair <int, int>> adj[MAX + 5];
bool endd[MAX + 5];
int travel_plan (int n, int m, int r[][2], int w[], int k, int e[]) {
for (int i = 1; i <= n; i++) {
adj[i].clear();
endd[i] = 0;
}
for (int i = 0; i < m; i++) {
adj[r[i][0] + 1].push_back({r[i][1] + 1, w[i]});
adj[r[i][1] + 1].push_back({r[i][0] + 1, w[i]});
}
ll dist[n + 1][2];
for (int i = 1; i <= n; i++) dist[i][0] = dist[i][1] = inf;
priority_queue <vector <ll>, vector <vector <ll>>, greater <vector <ll>>> pq;
for (int i = 0; i < k; i++) {
e[i]++;
dist[e[i]][0] = dist[e[i]][1] = 0;
pq.push({0, 0, e[i]});
}
while (!pq.empty()) {
auto l = pq.top();
pq.pop();
if (dist[l[2]][0] < l[0]) continue;
if (dist[l[2]][1] < l[1]) continue;
for (auto j : adj[l[2]]) {
bool flag = 1;
if (j.second + l[0] < dist[j.first][1]) {
dist[j.first][0] = dist[j.first][1];
flag = 0;
dist[j.first][1] = j.second + l[0];
} else if (j.second + l[0] < dist[j.first][0]) {
flag = 0;
dist[j.first][0] = j.second + l[0];
}
if (!flag) pq.push({dist[j.first][0], dist[j.first][1], j.first});
}
}
return dist[1][0];
}
