//éªè±é£é£å風å¯å¯
//天å°ä¸çè¼è«
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
vector<ii> al[300005];
ii edge[300005];
ll w[300005];
ll p[300005];
ll fw[300005]; //dist 1->i
ll bw[300005]; //dist N->i
priority_queue<ii,vector<ii>,greater<ii> > pq;
bool used[300005];
int TIME;
int in[300005];
int low[300005];
bool dc[300005]; //whether will disconnect vertice 1 and N
vector<int> bridge;
void dfs(int i,int p){
in[i]=low[i]=TIME++;
if (i==n) dc[i]=true;
for (auto &it:al[i]){
if (it.fi==p || !used[it.se]) continue;
if (!in[it.fi]){
dfs(it.fi,i);
low[i]=min(low[i],low[it.fi]);
if (dc[it.fi]){
if (in[it.fi]==low[it.fi]) bridge.push_back(it.se);
dc[i]=true;
}
}
else{
low[i]=min(low[i],in[it.fi]);
}
}
}
bool test(ll i){
if (i<fw[n]) return true;
rep(x,0,m){
used[x]=(fw[edge[x].fi]+w[x]+bw[edge[x].se]<=i ||
fw[edge[x].se]+w[x]+bw[edge[x].fi]<=i);
}
TIME=1;
bridge.clear();
memset(in,0,sizeof(in));
memset(dc,false,sizeof(dc));
dfs(1,-1);
for (auto &it:bridge){
if (fw[edge[it].fi]+w[it]+p[it]+bw[edge[it].se]>i &&
fw[edge[it].se]+w[it]+p[it]+bw[edge[it].fi]>i) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
rep(x,0,m){
cin>>edge[x].fi>>edge[x].se>>w[x];
al[edge[x].fi].push_back(ii(edge[x].se,x));
al[edge[x].se].push_back(ii(edge[x].fi,x));
}
rep(x,m,0) p[x]=max(p[x+1],w[x+1]);
memset(fw,63,sizeof(fw));
fw[1]=0;
pq.push(ii(fw[1],1));
while (!pq.empty()){
ll node=pq.top().se,weight=pq.top().fi;
pq.pop();
if (fw[node]!=weight) continue;
for (auto &it:al[node]){
if (fw[it.fi]>weight+w[it.se]){
fw[it.fi]=weight+w[it.se];
if (it.fi!=n) pq.push(ii(fw[it.fi],it.fi));
}
}
}
memset(bw,63,sizeof(bw));
bw[n]=0;
pq.push(ii(bw[n],n));
while (!pq.empty()){
ll node=pq.top().se,weight=pq.top().fi;
pq.pop();
if (bw[node]!=weight) continue;
for (auto &it:al[node]){
if (bw[it.fi]>weight+w[it.se]){
bw[it.fi]=weight+w[it.se];
if (it.fi!=1) pq.push(ii(bw[it.fi],it.fi));
}
}
}
ll lo=fw[n]-1,hi=fw[n]+1e9+10,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (test(mi)) lo=mi;
else hi=mi;
}
cout<<hi<<endl;
}
