#include<bits/stdc++.h>

#define R register int

using namespace std;

//const int inf=0x3f3f3f3f;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>'') if(ch=='-') f=-,ch=getchar();

    while(ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();

    return x*f;

}

int n,m,a[][],dis[],inf;

bool vis[];

inline void Run()

{

    memset(dis,0x3f,sizeof(dis));

    inf=dis[];

    dis[]=;

    for(R i=;i<n;i++)

    {

        int x=;

        for(R j=;j<=n;j++)

        {

            if((!vis[j])&&(x==||dis[j]<dis[x]))

            x=j;

        }

        vis[x]=;

        for(R k=;k<=n;k++)

        //if(a[x][k])

        dis[k]=min(dis[k],dis[x]+a[x][k]);

    }

}

int main()

{

    n=read();m=read();

    for(R i=;i<=n;i++)

     for(R j=;j<=n;j++)

      if(i==j) a[i][j]=;

      else a[i][j]=0x3f3f3f3f;//初始化

    for(R i=;i<=m;i++)

    {

        int x=read(),y=read(),z=read();

        a[x][y]=min(a[x][y],z);

    }

    Run();

    if(dis[n]>=inf/) cout<<"-1";

    else printf("%d",dis[n]);

    return ;

}