#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N=5001;
int d[N],v,w,n,m,x;
struct point{
    vector <int> to;
    vector <int> val;
}p[N];
//floyd的优化，超快！ 
int spfa()
{
    memset(d,127/3,sizeof(d));
    d[1]=0;
    queue <int> q;
    q.push(1);
    while (!q.empty())
    {
        x=q.front();//队首元素 
        q.pop();//弹出队首 
        for (int i=0;i<p[x].to.size();i++)//遍历该点连接的点 
        {
            v=p[x].to[i];
            w=p[x].val[i];
            if (d[v]>d[x]+w)
            {
                d[v]=d[x]+w;
                q.push(v);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int a,b,dis;
        scanf("%d%d%d",&a,&b,&dis);
        p[a].to.push_back(b);
        p[a].val.push_back(dis);
    }
    spfa();
    printf("%d\n",d[n]);
    return 0;
}