#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int dist[N];
int st[N];
int n, m;

int p[N];
struct edge
{
    int a, b ,w ;
    
    bool operator < (const edge &W) const
    {
        return w < W.w;
    }
}edges[N*2];

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}


signed main()
{
    cin >> n >> m;
    int res = 0x7f7f7f7f;
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if(x == 1 && y == n) res = min(res, z);
        edges[i] = {x, y, z};
    }
    sort(edges, edges + m);
    for(int i = 1; i <= n; i++) p[i] = i;
    //cout << res << endl;
	std::vector<edge> ans;
	
    for(int i = 0; i < m ;i++)
    {
        int a = edges[i].a, b = edges[i].b, w =edges[i].w;
        int pa = find(a), pb = find(b);
        int t = p[pa];
        if(pa != pb) 
        {
            p[pa] = pb;
        }
        int a1 = find(1), a2 = find(n);
        if(a1 == a2)
        {
            ans.push_back(edges[i]);
            p[pa] = t;
            st[i] = 1;
        }
    }
    int cnt = ans.size();
    //cout <<  << endl;
    /*for(int i = 0; i <ans.size(); i++){
    	int a = ans[i].a, b = ans[i].b, w =ans[i].w;
    	cout << a << ' ' << b << ' ' << w << endl;
    }*/
    for(int i = 1; i <= n; i++) p[i] = i;
    
    for(int i = 0; i < m ;i++)
    {	
    	if(st[i]) continue;
        int a = edges[i].a, b = edges[i].b, w =edges[i].w;
        int pa = find(a), pb = find(b);
        int t = p[pa];
        if(pa != pb) 
        {
            p[pa] = pb;
        }
        for(int j = 0; j < cnt;j++){
        		int sa = ans[j].a, sb = ans[j].b, sw =ans[j].w;
        int psa = find(sa), psb = find(sb);
        t = p[psa];
        if(psa != psb) 
        {
            p[psa] = psb;
        }
        int a1 = find(1), a2 = find(n);
        if(a1 == a2)
        {
            res = min(res, w + sw);
            p[psa] = t;
            cnt = j;
        }
        	
        }
    }
    cout << res <<endl;
}