堆优化的最短路径，其实可以用SPFA做的，效果会相当会
//堆优化的最短路径不知道什么原因的AC

#include <stdio.h>

const int MAX_N = 30005;

const int MAX_M = 150005;

const int MAX = 0x7fffffff;


//邻接链表部分
struct
{
    int next;
    int last;
}head[MAX_N];

struct
{
    int val;
    int len;
    int next;
}point[MAX_M];
int now;

void initm ( int n )
{
    
    now = 0;
    for ( int i=0; i<n; i++ )
    {
        head[i].next = head[i].last = -1;
    }
}

void add ( int a, int b, int l )
{
    
    point[now].val = b;
    point[now].len = l;
    point[now].next = -1;
    if ( head[a].next == -1 )
    {
        head[a].next = now;
    }
    else
    {
        point[ head[a].last ].next = now;
    }
    head[a].last = now ++;
}

//堆部分
typedef struct
{
    int val;
    int addr;
}type;
type heap[MAX_N];
int hnow;

int hash[MAX_N];//记录元素在堆中的位置

void inith ()//初始化堆
{
    
    hnow = 0;
}

void swap ( type *a, type *b )//交换堆中元素
{
    type temp;
    temp.addr = a->addr;
    temp.val = a->val;
    a->addr = b->addr;
    a->val = b->val;
    b->addr = temp.addr;
    b->val = temp.val;
}

void cpy ( type *a, type *b )//复制
{
    
    a->addr = b->addr;
    a->val = b->val;
}

void done ( int p )//调整堆向上
{
    
    int fa;
    while ( 1 )
    {
        if ( p & 1 )
        {
            fa = p / 2;
        }
        else
        {
            fa = (p - 1) / 2;
        }
        
        if ( p == 0 || heap[p].val > heap[fa].val )
        {
            return;
        }

        hash[ heap[p].addr ] = fa;
        hash[ heap[fa].addr ] = p;
        swap ( &heap[p], &heap[fa] );

        p = fa;
    }
}

void ins ( type *in )//插入
{
    hash[ in->addr ] = hnow;
    cpy ( &heap[hnow], in );
    int p = hnow ++;
    done ( p );
}

void del ( int p )
{

    hash[ heap[hnow-1].addr ] = p;
    cpy ( &heap[p], &heap[hnow-1] );
    hnow --;

    int ls, rs;
    int flag = 1;
    while ( flag )
    {
        flag = 0;
        ls = p * 2 + 1;
        rs = p * 2 + 2;
        if ( ls < hnow && rs < hnow )
        {
            if ( heap[ls].val < heap[rs].val && heap[ls].val < heap[p].val )
            {
                hash[ heap[p].addr ] = ls;
                hash[ heap[ls].addr ] = p;
                swap ( &heap[p], &heap[ls] );
                p = ls;
                flag = 1;
            }
            else if ( heap[rs].val < heap[ls].val && heap[rs].val < heap[p].val )
            {
                hash[ heap[p].addr ] = rs;
                hash[ heap[rs].addr ] = p;
                swap ( &heap[p], &heap[rs] );
                p = rs;
                flag = 1;
            }
        }
        else if ( ls < hnow  && rs >= hnow )
        {
            if ( heap[ls].val < heap[p].val )
            {
                hash[ heap[p].addr ] = ls;
                hash[ heap[ls].addr ] = p;
                swap ( &heap[p], &heap[ls] );
                p = ls;
                flag = 1;
            }
        }
    }
}

//最短路径部分

int used[MAX_N];

void initdj ( int s, int n )
{

    for ( int i=0; i<n; i++ )
    {
        used[i] = 0;
    }
}

int dj ( int s, int t, int n )
{

    initdj ( s, n );
    int next;
    
    inith ();
    for ( int i=0; i<n; i++ )
    {
        type in;
        if ( i != s )
        {
            in.addr = i;
            in.val = MAX;
        }
        else
        {
            in.addr = i;
            in.val = 0;
        }
        ins ( &in );
    }

    for ( int i=0; i<n; i++ )
    {
        next = heap[0].addr;
        used[ heap[0].addr ] = 1;
        int dis = heap[0].val;
        if ( next == t )
        {
            break;
        }
        del ( 0 );

        for ( int j=head[next].next; j!=-1; j=point[j].next )
        {
            if ( ! used[ point[j].val ] )
            {
                if ( heap[ hash[ point[j].val ] ].val > dis + point[j].len )
                {
                    heap[ hash[ point[j].val ] ].val = dis + point[j].len;
                    done ( hash[ point[j].val ] );
                }
            }
        }
    }
    return heap[0].val;
}

int main ()
{

    int n, m;
    int b, e, l;

    while ( scanf ( "%d%d", &n, &m ) != EOF )
    {
        initm ( n );
        for ( int i=0; i<m; i++ )
        {
            scanf ( "%d%d%d", &b, &e, &l );
            add ( b-1, e-1, l );
        }
        printf ( "%d\n", dj ( 0, n-1, n ) );
    }
    return 0;
}