#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

int n, m, u, v, w;
vector<pii> graph[5001];
bool visited[5001];
int dist[5001], dist2[5001];

void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, 1});
    dist[1] = 0;
    memset(dist, 0x3f, sizeof(dist));
    memset(dist2, 0x3f, sizeof(dist2));
    while(!q.empty()){
        auto nownode = q.top();
        q.pop();
        int v = nownode.y, d = nownode.x;
        if(visited[v]) continue;//
        if(dist2[v] < d) continue;
        for(auto nextnode : graph[v]){
            if(visited[nextnode.x]) continue;//
            int d2 = d + nextnode.y;
            if(dist[nextnode.x] > d2){
                swap(dist[nextnode.x], d2);
                q.push({dist[nextnode.x], nextnode.x});
            }
            if(dist2[nextnode.x] > d2 && dist[v] < d2){
                dist2[nextnode.x] = d2;
                q.push({dist2[nextnode.x], nextnode.x});
            }
        }
    }   
    return;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    dijkstra();
    cout << dist2[n] << endl;
    return 0;
}