#include <array>
#include <vector>
#include <iostream>
#include <list>
#include <algorithm>
#include <queue>
#include <climits>

const unsigned long long INF = ULONG_MAX;

using namespace std;

struct comp {
    bool operator()(const pair<int, unsigned long long> &a, const pair<int, unsigned long long> &b) {
        return a.second > b.second;
    }
};
//g - список смежности
//d массив меток
//u массив посещений
//pq minheap
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<list<pair<int, unsigned long long> > > g(n);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x - 1].emplace_back(pair<int,unsigned long long>(y-1,z));
        g[y - 1].emplace_back(pair<int,unsigned long long>(x-1,z));
    }
    priority_queue<pair<int, unsigned long long>, vector<pair<int, unsigned long long>>, comp> pq;
    vector<unsigned long long> d(n, INF);
    d[0] = 0;
    vector<bool> u(n);
    int v = 0;
    pq.push(pair<int, unsigned long long>(0, 0));
    //for (int i = 0; i < n; ++i) {
    while(!pq.empty()){
        v = pq.top().first;
        pq.pop();
        if (!u[v]) {
            u[v] = true;
            for_each(g[v].begin(), g[v].end(), [&u, &d, &v, &pq](pair<int, unsigned long long> &pair1) {
                int to = pair1.first;
                unsigned long long len = pair1.second;
                if (!u[to] && d[v] != INF && d[v] + len < d[to]) {
                    d[to] = d[v] + len;
                    pq.push(pair<int, unsigned long long>(to, d[to]));
                }
            });
        }
    }
    cout << d[n-1];
}