/*
1. 稀疏图用邻接表形式存储
2. 求单源最短路, 其他点有的离源点近, 有的远, 所以贪心的求最近的点的最短路,并扩展到最后
3. 找到离源点最近的点, 那么可以把其放入最小堆中, 堆顶是最近的点, 然后扩展相邻的所有点, 并把扩展成功的点放入堆中
*/


import java.util.*;

public class Main{

    static final int INF = Integer.MAX_VALUE >> 1;
    class Edge{
        int x,y,d;
        public Edge(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    class Node{
        int x, d;
        public Node(int x, int d){
            this.x = x;
            this.d = d;
        }
    }
    void run(){
        int n = jin.nextInt();
        int m = jin.nextInt();

        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0 ; i < n ; i++) graph.add(new ArrayList<Edge>());
        for (int i = 0 ; i < m ; i++){
            int x = jin.nextInt() - 1;    
            int y = jin.nextInt() - 1;
            int z = jin.nextInt() ;

            graph.get(x).add(new Edge(x, y, z));
            // graph.get(y).add(new Edge(y, x, z));
        }

        int[] res = dijkstra(graph, 0);
        int ans = res[n-1] == INF ? -1 : res[n-1];
        System.out.println(ans);
    }


    public int[] dijkstra(List<List<Edge>> graph, int s){
        int n  = graph.size();
        boolean[] visit = new boolean[n];
        int[] dist = new int[n];
        Queue<Node> queue = new PriorityQueue<>((a,b)->(a.d-b.d));

        Arrays.fill(dist, INF);
        dist[s] = 0;
        queue.offer(new Node(s, 0));

        while (!queue.isEmpty()){
            int x = queue.poll().x;
            if (visit[x]) continue;
            visit[x] = true;
            List<Edge> edges = graph.get(x);
            for (int i = 0 ; i < edges.size(); i ++){
                Edge edge = edges.get(i);
                int y = edge.y;
                if (dist[y] > dist[x] + edge.d ){
                    dist[y] = dist[x] + edge.d;
                    queue.offer(new Node(y, dist[y]));
                }
            }
        }
        return dist;
    }

    private Scanner jin = new Scanner(System.in);
    public static void main(String[] args) {new Main().run();}
}