#include<iostream>
using namespace std;

#define max 0x70ffffff
int map[105][105];
int visit[105];
int dis[105];

int main()
{
    int n, m, a, b, c;
    int i, j, k;
    int min;
    while ( scanf("%d%d", &n, &m) && !( n ==0 && m == 0) ) {
        for ( i = 1; i <= n; i++ ) {
            for ( j = 0; j <= n; j++ )
                map[i][j] = max;
            visit[i] = 0;
        }
        for ( i = 0; i < m; i++ ) {
            scanf( "%d%d%d", &a, &b, &c );
            map[a][b] = map[b][a] = c;
        }
        for ( i = 1; i <= m; i++ )
            dis[i] = map[1][i];
        visit[1] = 1;
        dis[1] = 0;
        for ( i = 1; i <= m; i++ ) {
            min = max;
            for ( j = 1; j <= m; j++ ) {
                if ( dis[j] < min && !visit[j] ) {
                    min = dis[j];
                    k = j;
                }
            }
            if ( min == max ) break;
            visit[k] = 1;
            for( j = 1; j <= n; j++ ) {
                  if( min + map[k][j] < dis[j] && !visit[j] )
                      dis[j] = min + map[k][j];
            }
        }
        printf("%d\n", dis[n]);
    }

    return 0;
}