#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 100005;
vector<ii> adj[MAXN];
ll dist[MAXN][2];
int numNode, numEdge, numExit;
struct State {
ll dis;
int u, typ;
bool operator < (const State &s) const {
return dis > s.dis;
}
};
int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
numNode = _N, numEdge = _M, numExit = _K;
for (int i = 0; i < numEdge; ++i) {
int u(_R[i][0]), v(_R[i][1]), w(_L[i]);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 0; i < numNode; ++i)
dist[i][0] = dist[i][1] = 1e18;
priority_queue<State> heap;
for (int i = 0; i < numExit; ++i) {
int u(_P[i]);
dist[u][0] = dist[u][1] = 0;
heap.push({0, u, 1});
}
while(heap.size()) {
ll dis(heap.top().dis);
int u(heap.top().u), type(heap.top().typ);
heap.pop();
if(dis != dist[u][type])
continue;
for (int it = 0; it < int(adj[u].size()); ++it) {
int v(adj[u][it].fi), w(adj[u][it].se);
if(dist[v][0] > dis + w) {
if(dist[v][0] != dist[v][1] && dist[v][0] < 1e18) {
dist[v][1] = dist[v][0];
heap.push({dist[v][1], v, 1});
}
dist[v][0] = dis + w;
} else
if(dist[v][1] > dis + w) {
dist[v][1] = dis + w;
heap.push({dis + w, v, 1});
}
}
}
return dist[0][1];
}
