#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'
const int N = 3e5+1;
vector<tuple<int,int,int>> g[N];
tuple<int,int,int> e[N];
int d1[N], dn[N], p[N], vis[N], tin[N], low[N], tf[N];
vector<int> brg;
int n, cnt;
int dfs(int v, int p){
vis[v] = 1;
tin[v] = low[v] = cnt++;
int ft = (v == n);
for(auto [ch, w, i] : g[v]){
if(!tf[i] or ch == p) continue;
if(vis[ch]){
low[v] = min(low[v], tin[ch]);
continue;
}
int res = dfs(ch, v);
ft |= res;
low[v] = min(low[v], low[ch]);
if(res and tin[v] < low[ch]) brg.push_back(i);
}
return ft;
}
inline void solve(){
int m;
cin>>n>>m;
for(int i=0; i<m; i++){
int a, b, w;
cin>>a>>b>>w;
g[a].push_back({b, w, i});
g[b].push_back({a, w, i});
e[i] = {a, b, w};
}
int mx = 0;
for(int i=m-1; i>=0; i--){
auto [a, b, w] = e[i];
p[i] = mx;
mx = max(mx, w);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
fill(d1, d1+n+1, inf);
pq.push({0, 1});
d1[1] = 0;
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(d1[v] != d) continue;
for(auto [ch, w, i] : g[v]){
if(d + w < d1[ch]){
d1[ch] = d + w;
pq.push({d1[ch], ch});
}
}
}
fill(dn, dn+n+1, inf);
pq.push({0, n});
dn[n] = 0;
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(dn[v] != d) continue;
for(auto [ch, w, i] : g[v]){
if(d + w < dn[ch]){
dn[ch] = d + w;
pq.push({dn[ch], ch});
}
}
}
int lo = d1[n], hi = d1[n] + p[0];
while(lo < hi){
int md = (lo+hi+1)/2;
for(int i=0; i<m; i++){
auto [a, b, w] = e[i];
tf[i] = (min(d1[a] + dn[b], d1[b] + dn[a]) + w < md);
}
fill(vis, vis+n+1, 0);
brg.clear();
cnt = 0;
dfs(1, 0);
int pos = !vis[n];
for(int i : brg){
auto [a, b, w] = e[i];
pos |= (min(d1[a] + dn[b], d1[b] + dn[a]) + w + p[i] >= md);
}
if(pos) lo = md;
else hi = md-1;
}
cout<<lo;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
