import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 1000010;
    static int[] e, ne, w, adj, dist; //临接表可以忽略重边和自环问题
    static int idx = 0, n, INF = 0x3f3f3f3f;
    static boolean[] vi;
    public static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c; ne[idx] = adj[a]; adj[a] = idx++;
    }

    public static int dijkstra(){
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        Arrays.fill(dist, INF);
        pq.offer(new int[]{0,1});
        while(!pq.isEmpty()){
            int[] poll = pq.poll();
            int distance = poll[0];
            int node = poll[1];
            if(vi[node]) continue;
            vi[node] = true;
            for(int i = adj[node]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] > distance + w[i]){
                    dist[j] = distance + w[i];
                    pq.offer(new int[]{dist[j], j});
                }
            }
        }
        if(dist[n] == INF)  return -1;
        return dist[n];
    }

    public static void main(String[] args) throws Exception{
        e = new int[N]; ne = new int[N]; w = new int[N]; adj = new int[N];
        dist = new int[N]; vi = new boolean[N];
        String[] s = read.readLine().split(" ");
        Arrays.fill(adj, -1);
        n = Integer.valueOf(s[0]); int m = Integer.valueOf(s[1]);
        while(m -- > 0){
            s = read.readLine().split(" ");
            int a = Integer.valueOf(s[0]);
            int b = Integer.valueOf(s[1]);
            int c = Integer.valueOf(s[2]);
            add(a, b, c);
        }
        System.out.println(dijkstra());
    }

}