#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i=(a), _b=(b); i<=_b; i++)
#define FORD(i, a, b) for(int i=(a), _b=(b); i>=_b; i--)
#define BIT(i, j) ((i>>j)&1)
#define pb push_back
#define ii pair<ll, ll>
#define pii pair<ll, ii>
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const ll inf = 1e18;
const ll mod = 1e9+7;
const ll N = 300005;
const ll M = 50005;
int n, m;
ll w[N];
vector<ii> adj[N];
priority_queue<ii, vector<ii>, greater<ii>> pq;
ll fs[N], ft[N], suf[N];
void dijkstra (int s, ll f[])
{
fill (f + 1, f + n + 1, inf);
f[s] = 0;
pq.push ({0, s});
while (!pq.empty())
{
auto [du, u] = pq.top(); pq.pop();
if (du != f[u]) continue;
for (auto [v, id] : adj[u])
{
if (f[v] > f[u] + w[id])
{
f[v] = f[u] + w[id];
pq.push ({f[v], v});
}
}
}
}
int num[N], low[N], timeDfs;
vector<ii> g[N];
bool dfs (int u, int id, ll x)
{
num[u] = low[u] = ++timeDfs;
for (auto [v, vid] : g[u])
{
if (vid == id) continue;
if (!num[v])
{
if (dfs (v, vid, x)) return true;
low[u] = min (low[u], low[v]);
if (low[v] == num[v])
{
if (w[vid] + fs[u] + ft[v] + suf[vid] > x || ft[u] + fs[v] + w[vid] + suf[vid] > x)
return true;
}
}
else
{
low[u] = min (low[u], num[v]);
}
}
return false;
}
bool check (ll x)
{
for (int i = 1; i <= n; i++)
{
g[i].clear();
num[i] = low[i] = 0;
}
timeDfs = 0;
for (int u = 1; u <= n; u++)
{
for (auto [v, id] : adj[u])
{
if (w[id] + fs[u] + ft[v] <= x || ft[u] + fs[v] + w[id] <= x)
{
//cout << id << '\n';
g[u].pb({v, id});
g[v].pb({u, id});
}
}
}
return dfs (1, 0, x);
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v >> w[i];
adj[u].pb({v, i});
adj[v].pb({u, i});
}
dijkstra (1, fs);
dijkstra (n, ft);
for (int i = m; i >= 1; i--) suf[i] = max(suf[i + 1], w[i + 1]);
ll l = fs[n], r = fs[n] + suf[1], ans = fs[n];
//cout << check (7) << '\n';
while (l <= r)
{
ll mid = l + r >> 1;
if (check(mid))
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << ans + 1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "beautiful"
if(fopen(task".inp", "r"))
{
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
if(fopen("task.inp", "r"))
{
freopen("task.INP", "r", stdin);
freopen("task.OUT", "w", stdout);
}
solve();
return 0;
}
