#include<stdio.h>
#include<string.h>
#include<stdbool.h>

#define N 150010
#define INF 0x3f3f3f3f

int n, m;
int dist[N];
bool st[N];

typedef struct PII{
    int node;
    int dist;
}PII;
PII heap[N];
int size;

int h[N], cnt;
struct edge{
    int to;
    int next;
    int weight;
}E[N];

void add(int v, int w, int weight){
    E[++cnt].next = h[v];
    E[cnt].to = w;
    E[cnt].weight = weight;
    h[v] = cnt;
}

void down(int x){
    int t = x;
    if (2 * x <= size && heap[2 * x].dist < heap[t].dist)     t = 2 * x;
    if (2 * x + 1 <= size && heap[2 * x + 1].dist < heap[t].dist) t = 2 * x + 1;
    if (t != x){
        PII temp = heap[x];
        heap[x] = heap[t];
        heap[t] = temp;
        down(t);
    }
}

void up(int x){
    while (x / 2 && heap[x / 2].dist > heap[x].dist){
        PII temp = heap[x];
        heap[x] = heap[x / 2];
        heap[x / 2] = temp;
        x >>= 1;
    }
}

void heap_insert(int dist, int node){
    heap[++size].node = node;
    heap[size].dist = dist;
    up(size);
}

void heap_delete(){
    heap[1] = heap[size--]; 
    down(1);
}

int dijkstra_heap(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    heap_insert(0, 1);

    while (size){
        PII t = heap[1];
        heap_delete();

        int var = t.node, distance = t.dist;
        if (st[var]) continue;
        st[var] = true;

        for (int i = h[var]; i != -1; i = E[i].next){
            int j = E[i].to;
            if (dist[j] > distance + E[i].weight){
                dist[j] = distance + E[i].weight;
                heap_insert(dist[j], j);
            }
        }
    }

    if (dist[n] == INF)  return -1;
    else return dist[n];
}

int main(){

    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i++){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        add(a, b, w);
    }

    printf("%d", dijkstra_heap());

    return 0;
}