#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int maxN = 1e6 + 5;
int n, m, k, p[maxN];
struct Tedge
{
int u, v;
ll w;
}
e[maxN];
vector<int> adj[maxN];
ll d1[maxN], d2[maxN];
struct Titem
{
int v;
ll dlab;
bool operator < (const Titem& other) const
{
return dlab > other.dlab;
}
bool valid()
{
return dlab == d2[v];
}
};
priority_queue<Titem> pq;
void Dijkstra()
{
fill(d1 + 1, d1 + n + 1, 1e18);
fill(d2 + 1, d2 + n + 1, 1e18);
for (int i = 1; i <= k; ++i)
{
d1[p[i]] = d2[p[i]] = 0;
pq.push({p[i], d1[p[i]]});
}
while (!pq.empty())
{
Titem tmp = pq.top(); pq.pop();
if (!tmp.valid()) continue;
int u = tmp.v;
//cerr << u << " " << d2[u] << "\n";
if (u == 1) return;
for (int i : adj[u])
{
int v = e[i].u ^ e[i].v ^ u;
if (d1[v] > d2[u] + e[i].w)
{
if (d1[v] < d2[v])
{
d2[v] = d1[v];
pq.push({v, d2[v]});
}
d1[v] = d2[u] + e[i].w;
}
else if (d2[v] > d2[u] + e[i].w)
{
d2[v] = d2[u] + e[i].w;
pq.push({v, d2[v]});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n = N;
m = M;
k = K;
for (int i = 1; i <= m; ++i)
{
e[i].u = R[i - 1][0] + 1;
e[i].v = R[i - 1][1] + 1;
e[i].w = L[i - 1];
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
}
for (int i = 1; i <= k; ++i)
{
p[i] = P[i - 1] + 1;
}
Dijkstra();
return d2[1];
}
