#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
struct node{
	int num;
	int dis;
	bool operator > (const node &t) const
	{	
		if(dis != t.dis)
		return dis > t.dis;
	}
}tmp;
int dis[N];
int dis2[N];
int isv[N];
int isv2[N];
int n,m;
vector<node>tr[N];
void dij(int s)
{
	memset(dis,0x3f3f3f3f,sizeof dis);
	priority_queue<node,vector<node> , greater<node> > q;
	q.push({s,0});
	dis[s] = 0;
	while(!q.empty())
	{
		tmp = q.top();
		int x = tmp.num;//起点
		q.pop();
		if(isv[x] == 1)
			continue;
		isv[x] = 1;
//		cout<<x<<endl;
		for(int i = 0 ; i < (int)tr[x].size() ; i ++ )
		{
			node now = tr[x][i];
			int len = tr[x][i].dis;//边长
			int e = tr[x][i].num;//	
			int len1 = max(dis[x] , len);
			if(dis[e] > len1)
			{
				dis[e] = len1;
				q.push({e,dis[e]});
			}
		}
	}
}
void dij2(int s)
{
	memset(dis2 , 0x3f3f3f3f , sizeof dis2); 
	priority_queue<node,vector<node> , greater<node> > q;
	q.push({s,0});
	dis2[s] = 0;
	while(!q.empty())
	{
		tmp = q.top();
		int x = tmp.num;//起点
		q.pop();
		if(isv2[x] == 1)
			continue;
		isv2[x] = 1;
//		cout<<x<<endl;
		for(int i = 0 ; i < (int)tr[x].size() ; i ++ )
		{
			node now = tr[x][i];
			int len = tr[x][i].dis;//边长
			int e = tr[x][i].num;//	
			int len1 = max(dis2[x] , len);
			if(dis2[e] > len1)
			{
				dis2[e] = len1;
				q.push({e,dis2[e]});
			}
		}
	}
}
void solve() 
{
	cin >> n >> m;
	vector<array<int,3>>bian;
	for(int i = 0 ; i < m ; i ++){
		int u , v , dis;
		cin >> u >> v >> dis;
		tr[u].pb({v , dis});
		tr[v].pb({u , dis});
		bian.pb({u , v , dis});
	}
	dij(1);
	dij2(n);
	LL ans = 1e18;
	for(auto it: tr[1]){
		if(it.num == n){
			ans = it.dis;
		}
	}
	for(int i = 0 ; i < m ; i ++){
		int u = bian[i][0] , v = bian[i][1] , diss = bian[i][2];
		if(dis[u] <= diss && dis[v] <= diss)
		 	ans = min(ans ,1LL * diss + min(max(dis[u] , dis2[v]) , max(dis[v] , dis2[u])));
	}
	cout << ans;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	//cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}