#include <iostream>
#include <climits>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;
const int N=3e5+5;
struct Edge{
int u, v, w;
void tie(int &_u, int &_v, int &_w)
{
_u=u;
_v=v;
_w=w;
}
};
struct Node{
int v, w, id;
};
Edge edge[N];
vector<Node>g[N];
int n, m, u, v, w, mx[N], num[N], low[N], cnt, ok[N];
long long d1[N], dn[N], res, l, r, mid;
void JQK(int S, long long d[])
{
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
for(int i=1;i<=n;i++)
d[i]=LLONG_MAX;
d[S]=0;
q.push({0,S});
while(!q.empty())
{
auto [du,u]=q.top();
q.pop();
if(du!=d[u])
continue;
for(auto &e:g[u])
if(d[e.v]>du+e.w)
{
d[e.v]=du+e.w;
q.push({d[e.v],e.v});
}
}
}
vector<int>ans;
int dfs(int u, int pr=0)
{
num[u]=low[u]=++cnt;
int cc=(u==n);
for(auto &[v,w,id]:g[u])
if(v!=pr&&ok[id])
{
if(!num[v])
{
int tmp=dfs(v,u);
low[u]=min(low[u],low[v]);
if(tmp&&num[u]<low[v])
ans.push_back(id);
cc|=tmp;
}
else
low[u]=min(low[u],num[v]);
}
return cc;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
if(fopen("beautiful.inp", "r")) {
freopen("beautiful.inp", "r", stdin);
freopen("beautiful.out", "w", stdout); }
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
edge[i]={u,v,w};
g[u].push_back({v,w,i});
g[v].push_back({u,w,i});
}
for(int i=m-1;i;i--)
mx[i]=max(edge[i+1].w,mx[i+1]);
JQK(1,d1);
JQK(n,dn);
res=l=d1[n];
r=l+mx[1];
while(l<=r)
{
mid=(l+r)/2;
for(int i=1;i<=m;i++)
{
edge[i].tie(u,v,w);
ok[i]=(min(d1[u]+dn[v],d1[v]+dn[u])+w<mid);
}
for(int i=1;i<=n;i++)
num[i]=low[i]=0;
cnt=0;
ans.clear();
dfs(1);
cnt=!num[n];
for(auto i:ans)
{
edge[i].tie(u,v,w);
cnt|=(min(d1[u]+dn[v],d1[v]+dn[u])+w+mx[i]>=mid);
}
if(cnt)
{
l=mid+1;
res=mid;
}
else
r=mid-1;
}
cout<<res;
return 0;
}
