import java.util.Scanner;

public class Main
{
    private static int N=510;
    private static int n,m;
    private static int[][] g=new int[N][N];
    private static boolean[] st=new boolean[N];
    private static int[] dist=new int[N];
    private static int max=1000000000;

    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);

        n=scan.nextInt();
        m=scan.nextInt();

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    g[i][j]=0;
                else
                    g[i][j]=max;
            }
            dist[i]=max;
        }


        while(m--!=0)
        {
            int x=scan.nextInt();
            int y=scan.nextInt();
            int c=scan.nextInt();
            g[x][y]=Math.min(g[x][y],c);
        }

        int t=dijstra();

        System.out.println(t);

        scan.close();

    }
    /**
     * 1、循环i->  0-n次
     * 2、    在未确定的点j中->1-n  找到一个距离最近的点t
     * 3、    将找到的t加入确定集合s中
     * 4、    以找到的t,更新一遍最短的距离
     * 
     **/
    public static int dijstra()
    {
        dist[1]=0;

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

            st[t]=true;

            for(int j=1;j<=n;j++)
                dist[j]=Math.min(dist[j],dist[t]+g[t][j]);

        }

        if(dist[n]==max)
            return -1;
        else 
            return dist[n];

    }



}