package 图论搜索;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Dijkstra求最短路径优化版 {
    public static class MyComparator implements Comparator<Node>{
        @Override
        public int compare(Node o1, Node o2) {
            return o1.d<o2.d?-1:1;
        }
    }
    public static class Node{
        int v,d;//虽然可以通过点v确定出起点到v的距离d = dist[v],但是d也要用来存在于Q中排序使用
        public Node(int v, int d) {
            this.v = v;
            this.d = d;
        }
    }
    static int N = 100010,idx;
    static int h[] = new int[N];
    static int ne[] = new int[N];
    static int e[] = new int[N];
    static int dist[] = new int[N];
    static int w[] = new int[N];
    static boolean st[] = new boolean[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Arrays.fill(h, 1, n, -1);
        Arrays.fill(dist, 1, n, 0x3f3f3f3f);//填充
        while(m-->0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            add(a,b,c);//构造边
        }
        dist[1] = 0;
        PriorityQueue<Node> q = new PriorityQueue<>(new MyComparator());
        q.add(new Node(1,0));
        while(q.size()>0) {//第一次循环：把与起点联通的点加入队列当中（并初始化距离)，这些点是可以再次被更新的
            //已经加入st[] 集合当中的点，一定不会再次被更新（他们一定是最短距离)，假如出现负环则有可能会把st[]当中的点再次被更新
            Node head = q.poll();
            int v = head.v,d = head.d;
            if(st[v]) continue;
            st[v] = true;//在未访问集合中找到距离最小的点
            for(int j = h[v];j != -1;j = ne[j]) {
                int k = e[j];
                if(dist[k] > dist[v] + w[j]) {//dist[v]可以使用d代替
                    dist[k] = dist[v] + w[j];
                    q.add(new Node(k,dist[k]));//将被别的点更新过的点加入队列,再使用他去更新别人
                }
                //一直未被更新的点，要么是不联通的点，要么本身已是最短距离
            }
        }
        System.out.println(dist[n]==0x3f3f3f3f?-1:dist[n]);
    }
    private static void add(int a, int b, int c) {
        e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
    }
}