#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long long

const int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;

typedef long long ll;

const int N=300050;
const int M=1000050;

struct Edge{
	int to;
	int next;
	int w;
}edge[M<<1];

int cnt;
int head[N];
std::pair<int,int> dis1[N];
std::pair<int,int> dis2[N];
int n,m;

struct Node{
	int u;
	int w;
	int id;
	
	bool operator < (const Node& x) const {
		return x.w < w;
	}
};

inline void addedge(int u,int v,int w){
	edge[++cnt] = {v,head[u],w};
	head[u] = cnt;
	edge[++cnt] = {u,head[v],w};
	head[v] = cnt;
}

void Dijkstra(int s,std::pair<int,int> dis[]){
	fore(i,1,n+1){
		dis[i].fi = 2e9+5;
		dis[i].se = 0;
	}
	dis[s].fi = dis[s].se = 0;
	std::priority_queue<Node> q;
	q.push({s,0,0});
	while(!q.empty()){
		auto [u,d,ID] = q.top();
		q.pop();
		for(int i=head[u];i;i=edge[i].next){
			int v = edge[i].to , w = edge[i].w , id = i;
			if(w < d){
				w = d;
				id = ID;
			}
			if(dis[v].fi > w){
				dis[v].fi = w;
				dis[v].se = id;
				q.push({v,w,id});
			}
		}
	}
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    /* HeFei J */
    
    std::cin>>n>>m;
    fore(i,0,m){
    	int u,v,w;
    	std::cin>>u>>v>>w;
    	addedge(u,v,w);
    }
    Dijkstra(1,dis1);
    Dijkstra(n,dis2);
    int ans = INF;
    fore(u,1,n+1){
    	for(int i=head[u];i;i=edge[i].next){
    		int v = edge[i].to, w = edge[i].w;
    		if(dis1[u].fi > w || dis2[v].fi > w)	continue;
    		if(dis1[u].se == i || dis2[v].se == i)	continue;
    		ans = std::min(ans,w + std::max(dis1[u].fi,dis2[v].fi));
    	}
    }
    std::cout<<ans;
	return 0; 
}