最短路径算法
//面向邻接链表的DJ

#include <stdio.h>

const int MAX = 0x7fffffff;

struct
{
    int next;
    int last;
}head[1001];

typedef struct
{
    int next;
    int valu;
    int dis;
}type;
type p[40001];
int now;

void initm ( int n )
{

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

void add ( int b, int e, int d )
{

    p[now].next = -1;
    p[now].valu = e;
    p[now].dis = d;
    if ( head[b].next == -1 )
    {
        head[b].next = now;
    }
    else
    {
        p[ head[b].last ].next = now;
    }
    head[b].last = now ++;
}

int used[1001];

int dis[1001];

void initdj ( int s, int n, int *di )
{

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

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

    initdj ( s, n, di );
    
    int i, j;
    int now;

    for ( i=0; i<n; i++ )
    {
        type min;
        min.dis = MAX;
        for ( j=0; j<n; j++ )
        {
            if ( min.dis > di[j] && ! used[j] )
            {
                min.dis = di[j];
                min.valu = j;
            }
        }
        if ( min.valu == t )
        {
            break;
        }
        now = min.valu;
        used[ min.valu ] = 1;
        for ( j=head[now].next; j!=-1; j=p[j].next )
        {
            if ( ! used[ p[j].valu ] && di[ p[j].valu ] > di[now] + p[j].dis  )
            {
                di[ p[j].valu ] = di[now] + p[j].dis;
            }
        }
    }

    return di[t];
    
}

int main ()
{

    int t, n;
    int b, e, r;

    while ( scanf ( "%d%d", &t, &n ) != EOF )
    {
        initm ( n );
        for ( int i=0; i<t; i++ )
        {
            scanf ( "%d%d%d", &b, &e, &r );
            add ( b-1, e-1, r );
            add ( e-1, b-1, r );
        }

        printf ( "%d\n", dj ( n-1, 0, n, dis ) );

    }
    return 0;
}