import java.util.*;

class Node{
    int distance;
    int num;
    public Node(int distance,int num){
        this.distance=distance;
        this.num=num;
    }
}
public class Main {
    static int N = 100010;//边数M
    static int n,m;
    static int idx;
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] dist = new int[N];      //用于记录每一个点距离第一个点的距离
    static boolean[] st = new boolean[N];//用于记录该点的最短距离是否已经确定
    static int dijkstra(){
        for(int i=0;i<N;i++){
            dist[i]=0x3f3f3f;            //初始化距离  0x3f代表无限大
        }
        dist[1]=0;
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.distance<o2.distance?-1:1; //小根堆，取距离最小值
            }
        });
        pq.add(new Node(0,1));
        while(!pq.isEmpty()){
            Node t = pq.poll();
            int num = t.num;
            int distance = t.distance;
            if(st[num]) continue;
            st[num]=true;
            for(int i=h[num];i!=-1;i=ne[i]){
                int j = e[i];
                if(dist[j]>distance+w[i]){
                    dist[j]=distance+w[i];
                    pq.add(new Node(dist[j],j));
                }
            }
        }
        if(dist[n]==0x3f3f3f)   return -1; //如果第n个点路径为无穷大即不存在最低路径
        return dist[n];
    }
    static void add(int a,int b,int c){
        e[idx]=b;   w[idx]=c;   ne[idx]=h[a];   h[a]=idx++;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x,y,z);
        }
        System.out.print(dijkstra());
    }
}