// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 3e18 + 7;
const int maxn = 3e5 + 10;
int n, m, id = 0;
int isbrid[maxn], tin[maxn], tout[maxn], low[maxn], suffma[maxn];
vector<pair<int, int>> adj[maxn];
pair<pair<int, int>, int> edge[maxn];
vector<pair<int, int>> diadj[maxn];
vector<ll> dist1, distn;
inline vector<ll> dijkstra(int a){
vector<ll> dist(n + 1, INF);
dist[a] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
pq.push({0, a});
while(!pq.empty()){
int x = pq.top().se;
ll d = pq.top().fi;
pq.pop();
if(d > dist[x]) continue;
for(auto &elm: adj[x]){
if(dist[elm.fi] > d + elm.se){
dist[elm.fi] = d + elm.se;
pq.push({dist[elm.fi], elm.fi});
}
}
}
return dist;
}
inline void dfs(int a, int parid){
tin[a] = ++id;
low[a] = tin[a];
for(auto &elm: diadj[a]){
if(elm.se == parid) continue;
int x = elm.fi;
if(tin[x]){
low[a] = min(low[a], tin[x]);
}
else{
dfs(x, elm.se);
low[a] = min(low[a], low[x]);
if(low[x] >= tin[x] && tin[x] <= tin[n] && tin[n] <= tout[x]){
isbrid[elm.se] = 1;
}
}
}
tout[a] = id;
}
inline bool check(ll x){
if(dist1[n] >= x) return 1;
id = 0;
for(int i=1; i<=n; ++i){
diadj[i].clear();
tin[i] = low[i] = 0;
}
for(int i=1; i<=m; ++i){
isbrid[i] = 0;
int a = edge[i].fi.fi, b = edge[i].fi.se;
ll c = edge[i].se;
if(c + dist1[a] + distn[b] < x || c + dist1[b] + distn[a] < x){
diadj[a].push_back({b, i});
diadj[b].push_back({a, i});
}
}
dfs(1, -1);
for(int i=1; i<=m; ++i){
if(isbrid[i]){
int a = edge[i].fi.fi, b = edge[i].fi.se;
ll c = edge[i].se, d = suffma[i + 1];
ll num = min(c + d + dist1[a] + distn[b], c + d + distn[a] + dist1[b]);
if(num >= x) return 1;
}
}
return 0;
}
inline void solve(){
cin >> n >> m;
for(int i=1; i<=m; ++i){
int a, b, c;cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
edge[i] = {{a, b}, c};
}
for(int i=m; i>=1; --i) suffma[i] = max(suffma[i + 1], edge[i].se);
dist1 = dijkstra(1);
distn = dijkstra(n);
ll lo = 0, hi = (3e5 + 1) * 1e9 + 10;
ll ans = 0;
while(lo <= hi){
ll mid = (lo + hi) >> 1;
if(check(mid)){
ans = mid;
lo = mid + 1;
}
else hi = mid - 1;
}
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
