#include <stdio.h>

 #include <string.h>

 #define INF 0xfffffff

 int map[][];

 int dp[];

 char visit[];

 int main() {

     int n, m;

     int i, j, k, min;

     while (scanf("%d %d",&n,&m)!=EOF && (n||m)) {

         memset(visit, , sizeof(visit));

         for (i=; i<=n; ++i)

             for (j=; j<=n; ++j)

                 map[i][j] = INF;

         while (m--) {

             scanf("%d %d %d", &i, &j, &k);

             if (map[i][j] > k)

                 map[i][j] = map[j][i] = k;

         }

         for (i=; i<=n; ++i)

             dp[i] = map[][i];

         visit[] = ;

         for (i=; i<n; ++i) {

             min = INF;

             for (j=; j<=n; ++j) {

                 if ( !visit[j] && dp[j]<min) {

                     min = dp[j];

                     k = j;

                 }

             }

             visit[k] = ;

             for (j=; j<=n; ++j) {

                 if ( !visit[j] && min + map[k][j] < dp[j]) {

                     dp[j] = min + map[k][j];

                 }

             }

         }

         printf("%d\n", dp[n]);

     }

     return ;

 }