#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nn=3e5+10;
vector<pair<ll,ll>>XX[nn];
ll dis1[nn];//维护从1到每一个点的最小值 
ll dis2[nn];//维护从n开始到每一个点的最小值 
ll vis1[nn];//判断是否更新
ll vis2[nn]; 
ll n,m;
void bfs1(int x){
	priority_queue<pair<ll,ll>>X;
	X.push_back(x);
	memset(dis1,0x3f,sizeof dis1);
	dis1[x]=0;
	while(!X.empty()){
		pair<ll,ll>C=X.top();
		int id=C.second;
		X.pop_front();
		if(vis1[id])continue;
		vis1[id]++;
		for(auto ii:XX[id]){
			int ne=ii.first;
			ll val=ii.second;
			val=max(val,dis1[id]);
			if(val<dis1[ne]){
				dis1[ne]=val;
				X.push({-dis1[ne],ne});
			}
		}
	}
}
void bfs2(int x){
	priority_queue<pair<ll,ll>>X;
	X.push_back(x);
	memset(dis2,0x3f,sizeof dis2);
	dis2[x]=0;
	while(!X.empty()){
		pair<ll,ll>C=X.top();
		int id=C.second;
		if(vis2[id])continue;
		vis2[id]++;
		for(auto ii:XX[id]){
			int ne=ii.first;
			ll val=ii.second;
			val=max(val,dis2[id]);
			if(val<dis2[ne]){
				dis2[ne]=val;
				X.push({-dis2[ne],ne});
			}
		}
	}
}
struct node{
	ll u,v,w;
}A[nn];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;ll w;
		cin>>u>>v>>w;
		A[i].u=u;
		A[i].v=v;
		A[i].w=w;
		XX[u].push_back({v,w});
		XX[v].push_back({u,w});
	}
	bfs1(1);
	bfs2(n);
	ll an=1e18+10;
	for(int i=1;i<=m;i++){
		if(A[i].w>max(dis1[A[i].u],dis2[A[i].v]){
			an=min(A[i].w+max(dis1[A[i].u],dis2[A[i].v]),an);
		}
		if(A[i].w>max(dis1[A[i].v],dis2[A[i].u])){
			an=min(max(dis1[A[i].v],dis2[A[i].u]),an);
		}
	}
	cout<<an<<"\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}

answer.code: In function ‘void bfs1(int)’:
answer.code:13:11: error: ‘class std::priority_queue<std::pair<long long int, long long int> >’ has no member named ‘push_back’
   13 |         X.push_back(x);
      |           ^~~~~~~~~
answer.code:19:19: error: ‘class std::priority_queue<std::pair<long long int, long long int> >’ has no member named ‘pop_front’
   19 |                 X.pop_front();
      |                   ^~~~~~~~~
answer.code: In function ‘void bfs2(int)’:
answer.code:35:11: error: ‘class std::priority_queue<std::pair<long long int, long long int> >’ has no member named ‘push_back’
   35 |         X.push_back(x);
      |           ^~~~~~~~~
answer.code: In function ‘void solve()’:
answer.code:72:57: error: expected ‘)’ before ‘{’ token
   72 |                 if(A[i].w>max(dis1[A[i].u],dis2[A[i].v]){
      |                   ~                                     ^
      |                                                         )
answer.code:78:9: error: expected primary-expression before ‘}’ token
   78 |         }
      |         ^