#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18, maxn = 3e5 + 5;
vector<pair<int, int>> adj[maxn], g[maxn];
int d1[maxn], dn[maxn], wpro[maxn];
int tin[maxn], low[maxn], timer;
int has[maxn], mid, ok, n, m;
array<int, 3> edge[maxn];
void tarjan(int u, int p){
tin[u] = low[u] = ++timer;
has[u] = (u == n);
for(auto [v, id]: g[u]){
if(id == p) continue;
if(tin[v]) low[u] = min(low[u], tin[v]);
else{
tarjan(v, id);
low[u] = min(low[u], low[v]);
has[u] |= has[v];
if(low[v] == tin[v] && has[v]) ok |= (min(d1[u] + dn[v], d1[v] + dn[u]) + wpro[id] >= mid);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edge[i] = {u, v, w};
}
fill(d1 + 1, d1 + n + 1, inf);
fill(dn + 1, dn + n + 1, inf);
d1[1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 1});
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d > d1[u]) continue;
for(auto [v, w]: adj[u]){
if(d1[v] > d + w){
d1[v] = d + w;
pq.push({d1[v], v});
}
}
}
dn[n] = 0;
pq.push({0, n});
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d > dn[u]) continue;
for(auto [v, w]: adj[u]){
if(dn[v] > d + w){
dn[v] = d + w;
pq.push({dn[v], v});
}
}
}
int mx = edge[m][2];
for(int i = m - 1; i >= 1; i--){
wpro[i] = edge[i][2] + mx;
mx = max(mx, edge[i][2]);
}
auto check = [&]() -> bool {
timer = ok = 0;
for(int i = 1; i <= n; i++) tin[i] = 0, g[i].clear();
for(int i = 1; i <= m; i++){
auto [u, v, w] = edge[i];
if(min(d1[u] + w + dn[v], d1[v] + w + dn[u]) < mid){
g[u].push_back({v, i});
g[v].push_back({u, i});
}
}
tarjan(1, -1);
if(!tin[n]) return true;
return ok;
};
int l = d1[n], r = 2e15, ans = d1[n];
while(l <= r){
mid = (l + r) / 2;
if(check()) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans;
}
