import java.util.*;

public class Main{
    static int N = 510;
    static int n;
    static int[][] g = new int[N][N];//存储两点之间的距离，相当与代替邻接表来存储图
    static int[] dist = new int[N];//存储每个点到源点的最短距离
    static boolean[] bool = new boolean[N];//判断当前点是否被遍历过
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++){
                g[i][j] = 0x3f3f;
            }
        }
        while(m-- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            g[a][b] = Math.min(c,g[a][b]);
        }
        System.out.print(dijkstra());
    }
    static int dijkstra(){
        Arrays.fill(dist,0x3f3f);
        dist[1] = 0;//把自己的距离设置为0；
        for(int i = 0;i < n;i++){//循环遍历n次有n个点
            int t = -1;//没有找到当前循环的最短点
            for(int j = 1;j <= n;j++){
                if(!bool[j]&&(t == -1 ||dist[t] > dist[j] )){
                    t = j;//找到当前循环距离最短的点
                }
            }
            //找到最短点了；
            bool[t] = true;
            //最短点从新
            for(int j = 1;j <= n;j++){
                dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
            }
        }
        if(dist[n] == 0x3f3f){
            return -1;
        }else{
            return dist[n];
        }
    }

}