/*
-----------------------------------------------------------------------------
算法动画演示,可以看一看,脑中算法记清楚,手下算法不出错
https://www.bilibili.com/video/BV1q4411M7r9
-----------------------------------------------------------------------------
    Dijkstra算法步骤
    初始化dist[1]=0,dist[2~n]=无穷
    循环n次(0~n-1)or(0~n-2)也行
        1.循环n次(1~n)
            令t=(未访问过的&&距离当前最近的点)
        2.令st[t]=true,表示t点为已确定最短路的点
        3.循环n次(1~n)
            用t点更新其他点的距离dist[j]=min(dist[j],dist[t]+g[t][j]);
-----------------------------------------------------------------------------
    为什么(0~n-1)or(0~n-2)都可以，原因是当i=n-2时
    for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
    这一步必然已经更新了dis[n],因而i==n-1这一步可跳过
    手动模拟一遍就懂了
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];//已经确定最短路的点
int dijkstra(){
    memset(dist,0x3f,sizeof dist);//将距离初始化为无穷
    dist[1]=0;
    for(int i=0;i<n-1;i++){//对每个点循环处理一次
        int t=-1;
        for(int j=1;j<=n;j++)//找到距离当前节点最近的点
            if(!st[j]&&(t=-1||dist[j]<dist[t]))//t=-1保证初始化的成功
                t=j;
        st[t]=true;
        for(int j=1;j<=n;j++)//用t点做中转更新到其他点的距离
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]=0x3f3f3f) return -1;
    return dist[n];
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);//将图初始化，距离都是无穷
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);//两个点之间可能有多条边,取其中最小的一条
    }
    int t=dijkstra();
    cout<<t;
    return 0;
}