//#include "grader.h"
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
const int MAXN = 1e5 + 5;
vii gr[MAXN];
ll dist[MAXN];
bool visit[MAXN];
ll mn[MAXN];
const ll INF = 1e15;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
fill(gr, gr + MAXN, vii());
for (int i = 0; i < M; i++) {
gr[R[i][0]].pb(mp(R[i][1], L[i]));
gr[R[i][1]].pb(mp(R[i][0], L[i]));
}
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
fill(dist, dist + MAXN, INF);
memset(visit, false, sizeof visit);
for (int i = 0; i < K; i++) {
visit[P[i]] = true;
pq.push(mp(0, P[i]));
}
while (!pq.empty()) {
ll w = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (visit[u]) {
if (dist[u] == INF) {
dist[u] = w;
} else {
continue;
}
} else {
visit[u] = true;
continue;
}
for (auto v : gr[u]) {
if (dist[v.fi] == INF) {
pq.push(mp(w + v.se, v.fi));
}
}
}
return dist[0];
/*
fill(mn, mn + MAXN, INF);
for (int i = 0; i < K; i++) {
mn[P[i]] = 0;
dist[P[i]] = 0;
pq.push(mp(0, P[i]));
}
while (!pq.empty()) {
ll w = pq.top().fi;
int u = pq.top().se;
pq.pop();
if (dist[u] < w) continue;
for (auto v : gr[u]) {
ll cost = w + ( ll )v.se;
if (cost < mn[v.fi] || cost < dist[v.fi]) {
if (cost < mn[v.fi]) {
dist[v.fi] = mn[v.fi];
mn[v.fi] = cost;
} else if (cost < dist[v.fi]) {
dist[v.fi] = cost;
}
if (dist[v.fi] < INF)
pq.push(mp(dist[v.fi], v.fi));
}
}
}
assert(dist[0] < INF);
return (int)dist[0];
*/
}
