#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e5;
vector<pair<int,int>> adj[N];
int dist[N][2];
int travel_plan(int n, int m, int edges[][2], int t[], int k, int exits[]) {
for (int i=0;i<m;i++) {
adj[edges[i][0]].emplace_back(edges[i][1],t[i]);
adj[edges[i][1]].emplace_back(edges[i][0],t[i]);
}
set<pair<int,int>> q;
memset(dist,0x3f,sizeof(dist));
for (int i=0;i<k;i++) {
dist[exits[i]][0]=dist[exits[i]][1]=0;
q.insert(make_pair(0,exits[i]));
}
while(!q.empty()) {
int u=(*q.begin()).second;
int d=dist[u][1];
q.erase(q.begin());
for (auto &[v,len]: adj[u]) {
assert(dist[v][0]<=dist[v][1]);
if (d+len<dist[v][0]) {
q.erase(make_pair(dist[v][1],v));
dist[v][1]=dist[v][0];
dist[v][0]=d+len;
q.insert(make_pair(dist[v][1],v));
} else if (d+len<dist[v][1]) {
q.erase(make_pair(dist[v][1],v));
dist[v][1]=d+len;
q.insert(make_pair(dist[v][1],v));
}
}
}
return dist[0][1];
}
/*
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,k; cin >> n >> m >> k;
int edges[m][2],t[m],exits[k];
for (int i=0;i<m;i++) {
cin >> edges[i][0] >> edges[i][1] >> t[i];
}
for (int i=0;i<k;i++) {
cin >> exits[i];
}
int res; cin >> res;
assert(res==travel_plan(n,m,edges,t,k,exits));
}
*/
