import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.AbstractMap;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
    static int N = 1000010;
    static int [] h = new int[N];
    static int [] e = new int[N];
    static int [] ne = new int[N];
    static int [] w = new int[N];
    static int [] dist = new int[N];
    static boolean [] st = new boolean[N];
    //依据其距离按照自然顺序排列(小根堆)  <点|距离>
    static Queue<AbstractMap.SimpleEntry<Integer,Integer>> queue = new PriorityQueue<>((o1, o2) -> {
        Integer v1 = o1.getValue();
        Integer v2 = o2.getValue();
        return v1 - v2;
    });
    static int n, m, idx;
    static int inf = 0x3f3f3f3f;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        //初始化最短路径
        for (int i = 1; i <= n; i++) {
            dist[i] = inf;
        }

        //初始化邻接表头节点
        for (int i = 1; i <= n; i++)
            h[i] = -1;

        while (m -- > 0)
        {
            int a, b, c;
            String [] arr = reader.readLine().split(" ");
            a = Integer.parseInt(arr[0]);
            b = Integer.parseInt(arr[1]);
            c = Integer.parseInt(arr[2]);
            add(a, b, c);
        }
        System.out.println(dijkstra());
    }
    private static void add(int a, int b, int c)
    {
        e[idx] = b;
        w[idx] = c; //记录权值
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    private static int dijkstra()
    {
        dist[1] = 0;
        queue.add(new AbstractMap.SimpleEntry<>(1,0)); //由小根堆顶点开始遍历 第1个点的距离为0
        while (!queue.isEmpty())
        {
            AbstractMap.SimpleEntry<Integer, Integer> entry = queue.remove();
            int v = entry.getKey(); // 这个点
            if (st[v]) continue;  //这个点被访问过 换其他点 -->关键步骤！！防止超时
            st[v] = true;
            //当这个点未曾访问过，遍历这个点的所有出边
            for (int i = h[v]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[v] + w[i])   //当前点j的权值大于已经确定的点v的最短路径加上该点的权值
                {
                    dist[j] = dist[v] + w[i]; //更新最路径点为上一个确定点
                    queue.add(new AbstractMap.SimpleEntry<>(j,dist[j]));  //将该点对应最短路径和该点放进去
                }
            }
        }
        if (dist[n] == inf) return -1;
        return dist[n];
    }
}