#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 300005
#define ii pair<ll,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18;
int n, m;
struct edge
{
int u, v, w;
} a[MAXN];
vector<ii>g[MAXN];
namespace sub1
{
int timedfs;
int num[MAXN], low[MAXN];
ll cost[MAXN], d[2][MAXN];
vector<ii>adj[MAXN];
struct cmp
{
bool operator()(ii x, ii y)
{
return x.F > y.F;
}
};
bool minimize(ll &x, ll y)
{
if(x > y)
return x = y, 1;
return 0;
}
void bfs(int k, int st)
{
for(int i = 1; i <= n; i++)
d[k][i] = INF;
priority_queue<ii, vector<ii>, cmp>q;
q.push({0, st});
d[k][st] = 0;
while(sz(q))
{
ii top = q.top();
q.pop();
ll kc = top.F;
int u = top.S;
if(u != st && (u == n || u == 1))
continue;
for(ii i : g[u])
{
int v = i.F, id = i.S;
if(minimize(d[k][v], kc + a[id].w))
q.push({d[k][v], v});
}
}
}
bool dfs(int u, int p, ll L)
{
num[u] = low[u] = ++timedfs;
for(ii i : adj[u])
{
int v = i.F, id = i.S;
if(v == p)
continue;
if(num[v])
low[u] = min(low[u], num[v]);
else
{
if(dfs(v, u, L))
return 1;
low[u] = min(low[u], low[v]);
if(low[v] > num[u])
if(min(d[0][u] + d[1][v], d[0][v] + d[1][u]) + a[id].w + cost[id + 1] >= L)
return 1;
}
}
return 0;
}
bool check(ll L)
{
for(int i = 1; i <= n; i++)
{
num[i] = low[i] = 0;
vector<ii>().swap(adj[i]);
}
for(int i = 1; i <= m; i++)
{
if(a[i].u == n)
{
if(a[i].w + d[0][a[i].v] < L)
adj[a[i].u].push_back({a[i].v, i}), adj[a[i].v].push_back({a[i].u, i});
}
else
{
if(a[i].v == n)
{
if(d[0][a[i].u] + a[i].w < L)
adj[a[i].u].push_back({a[i].v, i}), adj[a[i].v].push_back({a[i].u, i});
}
else
{
if(a[i].u == 1)
{
if(a[i].w + d[1][a[i].v] < L)
adj[a[i].u].push_back({a[i].v, i}), adj[a[i].v].push_back({a[i].u, i});
}
else
{
if(a[i].v == 1)
{
if(a[i].w + d[1][a[i].u] < L)
adj[a[i].u].push_back({a[i].v, i}), adj[a[i].v].push_back({a[i].u, i});
}
else if(d[0][a[i].u] + a[i].w + d[1][a[i].v] < L || d[1][a[i].u] + a[i].w + d[0][a[i].v] < L)
adj[a[i].u].push_back({a[i].v, i}), adj[a[i].v].push_back({a[i].u, i});
}
}
}
}
// cout<<L<<":\n";
// for(int i=1;i<=n;i++)
// for(ii j:adj[i])
// cout<<i<<" "<<j.F<<" "<<a[j.S].w<<endl;
timedfs = 0;
return dfs(1, 0, L);
}
ll bina()
{
ll l = d[0][n], r = d[0][n] + 8;
while(l < r)
{
ll mid = (l + r + 1) / 2;
if(check(mid))
l = mid;
else
r = mid - 1;
}
return l;
}
void solve()
{
bfs(0, 1);
bfs(1, n);
for(int i = m; i >= 1; i--)
cost[i] = max(cost[i + 1], (ll)a[i].w);
cout << bina();
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
g[x].push_back({y, i});
g[y].push_back({x, i});
a[i] = {x, y, z};
}
sub1::solve();
}
