#include<iostream>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int M = 1000010;
int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
bool st[N];
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(int u, int dist[]){
    for(int i = 1; i <= n; i ++) dist[i] = 1e18;
    memset(st,false,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,u});
    dist[u]=0;
    while(q.size()){
        auto t = q.top();
        q.pop();
        int ver = t.second,distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j =e[i];
            if(dist[j] > max(w[i], distance)){
                dist[j] = max(w[i], distance);
                q.push({dist[j],j});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra(1, dist1);
    dijkstra(n, dist2);
    int ans = 1e18;
    for(int u = 1; u <= n; u ++){
    	for(int i = h[u]; ~i; i = ne[i]){
    		int v = e[i];
    		int t = max(dist1[u], dist2[v]);
    		if(w[i] >= t) ans = min(ans, w[i] + t);
		}
	}
    cout << ans;

    return 0;
}

answer.code:8:7: error: ‘N’ was not declared in this scope
    8 | int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
      |       ^
answer.code:8:12: error: ‘N’ was not declared in this scope
    8 | int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
      |            ^
answer.code:8:17: error: ‘N’ was not declared in this scope
    8 | int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
      |                 ^
answer.code:8:23: error: ‘N’ was not declared in this scope
    8 | int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
      |                       ^
answer.code:8:32: error: ‘N’ was not declared in this scope
    8 | int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
      |                                ^
answer.code:8:41: error: ‘N’ was not declared in this scope
    8 | int e[N],h[N],w[N],ne[N],dist1[N],dist2[N],n,m,idx;
      |                                         ^
answer.code:9:9: error: ‘N’ was not declared in this scope
    9 | bool st[N];
      |         ^
answer.code: In function ‘void add(long long int, long long int, long long int)’:
answer.code:11:5: error: ‘e’ was not declared in this scope
   11 |     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
      |     ^
answer.code:11:14: error: ‘w’ was not declared in this scope
   11 |     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
      |              ^
answer.code:11:23: error: ‘ne’ was not declared in this scope; did you mean ‘n’?
   11 |     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
      |                       ^~
      |                       n
answer.code:11:31: error: ‘h’ was not declared in this scope
   11 |     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
      |                               ^
answer.code: In function ‘void dijkstra(long long int, long long int*)’:
answer.code:15:12: error: ‘st’ was not declared in this scope; did you mean ‘std’?
   15 |     memset(st,false,sizeof st);
      |            ^~
      |            std
answer.code:25:19: error: ‘h’ was not declared in this scope
   25 |         for(int i=h[ver];i!=-1;i=ne[i]){
      |                   ^
answer.code:25:34: error: ‘ne’ was not declared in this scope; did you mean ‘n’?
   25 |         for(int i=h[ver];i!=-1;i=ne[i]){
      |                                  ^~
      |                                  n
answer.code:26:20: error: ‘e’ was not declared in this scope
   26 |             int j =e[i];
      |                    ^
answer.code:27:30: error: ‘w’ was not declared in this scope
   27 |             if(dist[j] > max(w[i], distance)){
      |                              ^
answer.code: In function ‘int main()’:
answer.code:38:12: error: ‘h’ was not declared in this scope
   38 |     memset(h,-1,sizeof h);
      |            ^
answer.code:45:17: error: ‘dist1’ was not declared in this scope
   45 |     dijkstra(1, dist1);
      |                 ^~~~~
answer.code:46:17: error: ‘dist2’ was not declared in this scope
   46 |     dijkstra(n, dist2);
      |                 ^~~~~
answer.code:49:35: error: ‘ne’ was not declared in this scope; did you mean ‘n’?
   49 |         for(int i = h[u]; ~i; i = ne[i]){
      |                                   ^~
      |                                   n
answer.code:50:25: error: ‘e’ was not declared in this scope
   50 |                 int v = e[i];
      |                         ^
answer.code:52:20: error: ‘w’ was not declared in this scope
   52 |                 if(w[i] >= t) ans = min(ans, w[i] + t);
      |                    ^