#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
void io() {
ios::sync_with_stdio(false);
cin.tie(NULL);
}
template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
void nop() {
cout << -1 << endl;
return;
}
const int N = 1e5+5 ;
int n , m , vis[N] ;
vector<pi> adj[N] ;
multiset<int> neigh[N] ;
int solve() {
priority_queue<array<int,2> , vector<array<int,2>> , greater<>> pq ;
vector<int> dist(n , 2e9) ;
for(int i = 0 ; i<n ; i++){
for(auto p : adj[i]){
if(vis[p.F]) neigh[i].insert(p.S) ;
}
if(neigh[i].size()>1){
int val = *next(neigh[i].begin()) ;
pq.push({val , i}) ;
dist[i] = val ;
}
}
while(!pq.empty()){
auto vec = pq.top() ; pq.pop() ;
int node = vec[1] , d = vec[0] ;
if(d!=dist[node] || vis[node]) continue;
vis[node] = 1 ;
for(auto p : adj[node]){
int to = p.F , w = p.S ;
if(vis[to]) continue;
neigh[to].insert(d + w) ;
if(neigh[to].size()>1){
int val = *next(neigh[to].begin()) ;
if(ckmin(dist[to] , val)) pq.push({val , to}) ;
}
}
}
return dist[0] ;
}
ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N ;
m = M ;
for(int i = 0 ; i<m ; i++){
int u = R[i][0] , v = R[i][1] , w = L[i] ;
adj[u].pb({v , w}) ;
adj[v].pb({u , w}) ;
}
for(int i = 0 ; i<K ; i++){
vis[P[i]] = 1 ;
}
return solve() ;
}
//int main() {
//#ifndef ONLINE_JUDGE
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
//#endif
// io();
// ll tt = 1;
// //cin>>tt ;
// while (tt--) {
// solve();
// }
//
// return 0;
//}
