#include <bits/stdc++.h>
#define int long long
#define arr3 array <int , 3>
#define pii pair <int , int>
#define fi first
#define se second
#define BIT(x , k) ((x >> k)&1)
#define MASK(x) (1 << x)
using namespace std;
const int maxn = 1e6 + 7;
const int INF = 1e18;
int n , m , mxe = 0 , max_w[maxn];
vector <arr3> edge;
vector <pii> g[maxn] , adj[maxn];
vector <int> dij(int st)
{
vector <int> d(n+1 , INF);
d[st] = 0;
priority_queue <pii , vector <pii> , greater <pii>> Q;
Q.push({0 , st});
while(!Q.empty())
{
int u = Q.top().se , c = Q.top().fi;
Q.pop();
if(c != d[u]) continue;
for(auto [v , w]: g[u])
{
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
Q.push({d[v] , v});
}
}
}
return d;
}
int timer = 0 , num[maxn] , low[maxn]; bool ok = 1;
vector <int> d1 , d2;
bool tarjan(int u , int p , int len)
{
num[u] = low[u] = ++timer;
bool has_n = (u == n);
for(auto [v , c]: adj[u])
{
if(v == p) continue;
if(num[v] == 0)
{
bool v_has_n = tarjan(v , u , len);
has_n |= v_has_n;
low[u] = min(low[u] , low[v]);
if(low[v] == num[v] && v_has_n && c > len) ok = 0;
}
else low[u] = min(low[u] , num[v]);
}
return has_n;
}
bool check(int len)
{
for(int i = 1; i <= n; i++) adj[i].clear() , num[i] = low[i] = 0;
for(int i = 0; i < m; i++)
{
auto &[u , v , w] = edge[i];
if(d1[u] + d2[v] + w > d1[v] + d2[u] + w) swap(u , v);
if(d1[u] + d2[v] + w <= len)
{
adj[u].push_back({v , d1[u] + d2[v] + w + max_w[i]});
adj[v].push_back({u , d1[u] + d2[v] + w + max_w[i]});
}
}
if(adj[1].empty()) return false;
timer = 0 , ok = 1;
tarjan(1 , 0 ,len);
return ok;
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u , v , w; cin >> u >> v >> w;
g[u].push_back({v , w});
g[v].push_back({u , w});
edge.push_back({u , v , w});
}
for(int i = m-2; i >= 0; i--) max_w[i] = max(max_w[i+1] , edge[i+1][2]);
d1 = dij(1);
d2 = dij(n);
int l = 0 , r = 4e14 , ans = 4e14;
while(l <= r)
{
int mid = (l+r)>>1;
if(check(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << '\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
