#include<algorithm>
#include<cstring>
#include<iostream>
#include<utility>

using namespace std;
typedef pair<int, int> PII;

int n, m, null = 0x3f3f3f3f;
const int N = 150150, M = 3 * N;

int h[N], e[M], w[M], ne[M];   // 邻接表
int idx = 0;

bool st[N];


PII heap[N];  // 堆
int ph[N], hp[N];
int sz = 0;

void insert(int x, int y, int z)
{
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

void heap_swap(int a, int b)
{
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    swap(ph[hp[a]], ph[hp[b]]);
}

void down(int x)
{
    int t = x;
    if (2 * x <= sz && heap[2 * x].second < heap[t].second) t = 2 * x;
    if (2 * x + 1 <= sz && heap[2 * x + 1].second < heap[t].second) t = 2 * x + 1;
    if (t != x) {
        heap_swap(t, x);
        down(t);
    }
}

void up(int x)
{
    // 模拟堆的那个题是否应该加上这个判断？
    if(x > sz) return;
    if (x / 2 && heap[x / 2].second > heap[x].second) {
        heap_swap(x / 2, x);
        up(x / 2);
    }
}

int dijkstra()
{
    for (int i = 1; i <= n; ++i) heap[i].first = i, heap[i].second = null, ph[i] = i, hp[i] = i;
    sz = n;
    heap[1].first = 1, heap[1].second = 0;
    down(1);
    while (sz) {
        const int t = heap[1].first, dist = heap[1].second;
        if (st[t]) continue;
        st[t] = true;
        heap_swap(1, sz--);
        down(1);
        for (int i = h[t]; ~i; i = ne[i]) {
            const int j = e[i];
            // 这里需要对j再判定一步，如果已经确定其最短路径了，无需再次更新
            // down是不会down的，但是会up上来
            // 如果不判定，也可以，那就需要修改up函数，x > sz时直接返回，不进行up操作
            // if (st[j]) continue;
            // 哪一种更合理些呢。。
            heap[ph[j]].second = min(heap[ph[j]].second, dist + w[i]);
            down(ph[j]), up(ph[j]);
        }
    }
    return heap[ph[n]].second == null ? -1 : heap[ph[n]].second;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    int x = 0, y = 0, z = 0;
    while (m--) {
        scanf("%d%d%d", &x, &y, &z);
        insert(x, y, z);
    }
    cout << dijkstra() << endl;
    return 0;
}