#include "crocodile.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll n, m, k;

vector<ii> Adj[N];

iiii cals[N];
//set<ii> cals[N];

bool ck[N];

ll mn_dist[N];

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 = 0; i < m; i++){
		Adj[R[i][0]].pb({R[i][1], L[i]});
		Adj[R[i][1]].pb({R[i][0], L[i]});		
	}
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for(int i = 0; i < n; i++){
		mn_dist[i] = oo;
		cals[i] = {{oo, oo}, {oo, oo}};
	}
	for(int i = 0; i < k; i++){
		ck[P[i]] = 1;
		mn_dist[P[i]] = 0;
		pq.push({0, P[i]});
	}
	while(!pq.empty()){
		int d = pq.top().fi, u = pq.top().se;
		//cout << d << " " << u << "\n";
		pq.pop();
		if(mn_dist[u] != d) continue;
		for(auto it : Adj[u]){
			int v = it.fi, w = it.se;
			ii temp = {mn_dist[u] + w, u};
			if(temp <= cals[v].fi){
				cals[v] = {temp, cals[v].fi};
			}
			else if(temp <= cals[v].se) cals[v] = {cals[v].fi, temp};
			//cals[v].insert({mn_dist[u] + w, u});
			if(cals[v].se.fi != oo){
				//set<ii>::iterator it = cals[v].begin();
				//it++;
				if(mn_dist[v] > cals[v].se.fi){
					mn_dist[v] = cals[v].se.fi;
					pq.push({mn_dist[v], v});
				}
			}
		}
	}
	return (mn_dist[0] == oo ? -1 : mn_dist[0]);
}

/*
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
*/