#include <bits/stdc++.h>
#define int long long
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
using namespace std;
const int N=5e5+5,mod1=1e9+7,mod=998244353,inf=1e18;
typedef pair<int,int> pi;

vector<pi>v[N];

int n,m;
vector<int> dij(int x){
    vector<int>dis(n+2,inf);
    vector<int>vis(n+2,0);
    priority_queue<pi, vector<pi>, greater<pi>>q;
    q.push({0,x});
    dis[x]=0;
    while (!q.empty()) {
		auto tmp = q.top();
		q.pop();
		int x = tmp.second;
		if (vis[x])continue;
		vis[x] = 1;
		for (int i = 0; i < v[x].size(); i++) {
			if (dis[v[x][i].first] > min(dis[v[x][i].first],max(dis[x],v[x][i].second))) {
				dis[v[x][i].first] = min(dis[v[x][i].first],max(dis[x],v[x][i].second));
				q.push({dis[v[x][i].first], v[x][i].first});
			}
		}
	}
    return dis;
}
vector<pair<int,pair<int,int>>>p;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        v[x].pb({y,z});
        v[y].pb({x,z});
        p.push_back({z,{x,y}});
    }
    vector<int>dis1=dij(1);
    vector<int>dis2=dij(n);
    int ans=1e18;
    for(auto i:p){
        int u=i.second.first;
        int v=i.second.second;
        vector<int>ww(3);
        ww[0]=i.first;
        ww[1]=dis1[u];
        ww[2]=dis2[v];
        sort(ww.begin(),ww.end());
        ans=min(ans,ww[1]+ww[2]);
        ww[0]=i.first;
        ww[1]=dis1[v];
        ww[2]=dis2[u];
        sort(ww.begin(),ww.end());
        ans=min(ans,ww[1]+ww[2]);
    }
    cout<<ans<<'\n';
}
signed main()
{
    io;
    int t=1;
   // cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}