#include <stdio.h>

 #include <iostream>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 #include <sstream>

 #define INF 1000000000

 using namespace std;

 int N, M;

 int dist[],g[][];

 int vis[];

 void dijkstra(int start)

 {

     for(int i=;i<=N;i++)

         dist[i]=INF;

     dist[start] = ;

     memset(vis,,sizeof(vis));

     while()

     {

         int mark=-,mindis=INF;

         for(int i=;i<=N;i++)

         {

             if(!vis[i]&&dist[i]<mindis)

             {

                 mindis=dist[i];

                 mark=i;

             }

         }

         if(mindis == INF)    // 找不到未收录的节点，则说明算法结束，退出

             break;

         vis[mark]=;

         for(int i=;i<=N;i++)

         {

             if(!vis[i])

             {

                 dist[i]=min(dist[i],dist[mark]+g[mark][i]);

             }

         }

     }

 }

 int main()

 {

     while(cin >> N >> M)

     {

         if(N ==  && M == )

             break;

         for(int i = ; i <= N; ++i)

             for(int j = ; j <= N; ++j)

             {

                 if(i == j)

                     g[i][j] = ;

                 else

                     g[i][j] = INF;

             }

         for(int i = ; i <= M; ++i)

         {

             int a,b,c;

             cin >> a >> b >> c;

             g[a][b] = g[b][a] = c;

         }

         dijkstra();

         cout << dist[N] << endl; 

     } 

     return ;

 }

 #include <stdio.h>

 #include <iostream>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <sstream>

 using namespace std;

 int dis[][];

 int main()

 {

        int N, M;

     while(cin >> N >> M)

     {

         if(N ==  && M == )

             break;

         for(int i = ; i <= N; ++i)

         {

             for(int j = ; j <= N; ++j)

             {

                 if(i == j)

                     dis[i][j] = ;

                 else

                     dis[i][j] = ;

             }

         }

         int a, b, c;

         for(int i = ; i <= M; ++i)

         {

             cin >> a >> b >> c;

             if(dis[a][b] > c)

                 dis[a][b] = dis[b][a] = c;

         }

         for(int k = ; k <= N; ++k)

             for(int i = ; i <= N; ++i)

                 for(int j = ; j <= N; ++j)

                 {

                     if(dis[i][j] > dis[i][k] + dis[k][j])

                         dis[i][j] = dis[i][k] + dis[k][j];

                 }

         cout << dis[][N] << endl;

     } 

     return ;

 }