/*
//程序时间复杂度O(n^2)
本题特点：①不存在负权边→朴素版dijktra算法
          ②点数小于边数->为稠密图->用邻接矩阵
必备知识：
          ①初始化邻接矩阵 d=0x3f3f3f3f 表示之间没有边
本题核心：
          用每次的还没有更新过其他点的dis最小的点更新其他的点（这个点之后是不会发生变化的了->因为更新它的那个点是上一次的能到它的并且到它的距离加上该点本身到原点的距离小于被更新的这个点到原点距离的那一次被更新过了的距离原点距离最小的那个点）
注意细节：
          ①两点之间可能有多个边，因此取最小的那个边
          //对应代码：
          //dist[i]=min(dist[i],dist[t]+g[t][i]);
          ②可能无法由原点到终点因此
          //对应代码
         // if(dist[n]== 0x3f3f3f3f) return -1;

*/


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N];
int dist[N];
int st[N];
int n,m;
int dijkstra()
{

    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    memset(st, 0, sizeof st);
    int t=0;
    while(t!=-1)
    {
    t=-1;
    for(int i=1;i<=n;i++)
    {
        if(!st[i]&&(t==-1||dist[i]<=dist[t]))
        {
            t=i;
        }
    }
    st[t]=1;
    if(t==-1) break;
    for(int i=1;i<=n;i++)
    {
        dist[i]=min(dist[i],dist[t]+g[t][i]);
    }

    }
    if(dist[n]== 0x3f3f3f3f) return -1;
    else return dist[n];

}
int main()
{

    cin>>n>>m;
    memset(g, 0x3f3f3f3f, sizeof g);
    while (m -- )
    {
        int x,y,z;
        scanf("%d%d%d", &x, &y,&z);
        g[x][y]=min(g[x][y],z);

    }
     int dd=dijkstra();
     cout<<dd<<endl;
}