#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXN=3*1e5;
struct we{
int u,v,w,wbuff;
};
vector<vector<we>> graph;
vector<long long> dijik(int s){
int n=graph.size()-1;
priority_queue<pair<long long,int>> pq;
vector<long long> dist;
dist.assign(n+1,-1);
dist[s]=0;
pq.push({0,s});
while(!pq.empty()){
int u=pq.top().second;
long long d=pq.top().first;
pq.pop();
if(d>dist[u]){
continue;
}
for(we &x:graph[u]){
int v=x.v,w=x.w;
if(dist[v]==-1||dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
pq.push({dist[v],v});
}
}
}
return dist;
}
bool brid[MAXN];
int low[MAXN+1],in[MAXN+1],sum[MAXN+1];
int tim=1;
vector<long long> d1,dn;
int n;
vector<we> edges;
void DFS(int u,int p){
in[u]=tim;
low[u]=tim;
tim++;
sum[u]=(u==1||u==n);
for(we &x:graph[u]){
int v=x.v;
if(v==p){
continue;
}
if(!in[v]){
DFS(v,u);
sum[u]+=sum[v];
low[u]=min(low[u],low[v]);
if(low[v]>in[u]&&sum[v]==1){
brid[x.w]=true;
}
}
else{
low[u]=min(low[u],in[v]);
}
}
}
bool check(long long mid){
int m=edges.size();
graph.clear(),graph.resize(n+1);
for(int i=0;i<m;i++){
int u=edges[i].u,v=edges[i].v,w=edges[i].w;
if(d1[u]+dn[v]+w<=mid||d1[v]+dn[u]+w<=mid){
graph[u].push_back({u,v,i,0});
graph[v].push_back({v,u,i,0});
}
}
memset(brid,false,sizeof(brid));
for(int i=1;i<=n;i++){
in[i]=0;
low[i]=0;
sum[i]=0;
}
tim=1;
DFS(1,-1);
bool flag=false;
for(int i=0;i+1<m;i++){
if(brid[i]){
int u=edges[i].u,v=edges[i].v,w=edges[i].w+edges[i].wbuff;
if(d1[u]+dn[v]+w>mid&&d1[v]+dn[u]+w>mid){
flag=true;
break;
}
}
}
return flag;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
cin >> n >> m;
edges.resize(m);
graph.resize(n+1);
int bst=0;
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
bst=max(bst,w);
graph[u].push_back({u,v,w,0});
graph[v].push_back({v,u,w,0});
edges[i]={u,v,w,0};
}
d1=dijik(1),dn=dijik(n);
edges[m-1].wbuff=0;
for(int i=m-2;i>=0;i--){
edges[i].wbuff=max(edges[i+1].wbuff,edges[i+1].w);
}
long long Low=d1[n],high=d1[n]+bst;
Low--,high++;
while(high-Low>1){
long long mid=((high-Low)>>1)+Low;
if(check(mid)){
Low=mid;
}
else{
high=mid;
}
}
cout << high;
}
