/*
1. 注意建图时可能有多条边,取最小的!!
2. 朴素dijkstra: 求单源最短路, 其他点有的离源点近, 有的远, 所以贪心的求最近的点的最短路, 并用其扩展其他点
*/


import java.util.*;


public class Main{
    int INF = Integer.MAX_VALUE >> 1;

    void run(){
        int n = jin.nextInt();
        int m = jin.nextInt();
        int[][] graph = new int[n][n];
        for (int i = 0 ; i < n ; i ++) Arrays.fill(graph[i], INF);

        for (int i = 0 ; i < m ; i ++){
            int x = jin.nextInt()-1;
            int y = jin.nextInt()-1;
            int z = jin.nextInt();
            graph[x][y] = Math.min(graph[x][y], z);
        }
        int[] res = dijkstra(graph, 0);
        int ans = res[n-1] == INF ? -1 : res[n-1];
        System.out.println(ans);
    }

    public int[] dijkstra(int[][] graph, int s){
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visit = new boolean[n];

        Arrays.fill(dist, INF);
        dist[s] = 0;

        for (int i = 0 ; i < n ; i ++){
            int t = -1;
            for (int j = 0 ; j < n ; j++)
                if (!visit[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;

            visit[t] = true;

            for (int j = 0; j< n ; j ++)
                dist[j] = Math.min(dist[j], dist[t] + graph[t][j]);
        }
        return dist;
    }

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