#include "crocodile.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<ll, ll>
#define xx first
#define yy second
#define INF 1000000000000010
#define MAXN 100010
using namespace std;
pii d[MAXN];
int n, m, k, p[MAXN];
bool bio[MAXN];
vector<pii> g[MAXN];
void upd(int u, ll x)
{
if (x<d[u].xx) { d[u].yy=d[u].xx; d[u].xx=x; }
else if (x<=d[u].yy) { d[u].yy=x; }
}
int dijkstra(int s)
{
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i=0; i<n; i++) d[i].xx=d[i].yy=INF;
for (int i=0; i<k; i++)
{
pq.push({0, p[i]});
d[p[i]].xx=0; d[p[i]].yy=0;
}
while (!pq.empty())
{
int u=pq.top().yy; pq.pop();
//cout<<"na vrhu mie "<<u<<" "<<d[u].xx<<" "<<d[u].yy<<endl;
if (bio[u]) continue;
bio[u]=true;
for (auto edge:g[u])
{
int v=edge.xx; ll len=edge.yy;
//upd(v, d[u]+len);
if (d[u].yy+len<d[v].yy)
{
//cout<<"sace apdejt "<<v<<" "<<d[v].xx<<" "<<d[v].yy<<endl;
upd(v, d[u].yy+len);
//cout<<"posle laganog apdejta "<<v<<" "<<d[v].xx<<" "<<d[v].yy<<endl;
pq.push({d[v].yy, v});
}
}
}
return d[0].yy;
}
int travel_plan(int nn, int mm, int r[][2], int ww[], int kk, int pp[])
{
n=nn; m=mm; k=kk;
for (int i=0; i<k; i++) p[i]=pp[i];
///dummy=n
for (int i=0; i<m; i++)
{
int u, v, w; u=r[i][0]; v=r[i][1]; w=ww[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
for (int i=0; i<k; i++)
{
g[n].pb({p[i], 0});
g[p[i]].pb({n, 0});
d[p[i]].xx=0; d[p[i]].yy=0;
}
ll ret=dijkstra(n);
//for (int i=0; i<n; i++) cout<<d[i].xx<<" "<<d[i].yy<<endl;
return ret;
}
/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7
*/
/*
5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/
