#include<iostream>

 #include<queue>

 #include<functional>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int N = 1e3+;

 const int INF = 1e7;

 typedef pair<int, int> pll;

 struct Node

 {

     int next;

     int s;

     Node(int nt, int d):next(nt), s(d){};

 };

 vector<Node> G[N];

 int dis[N];

 void dijkstra()

 {

     priority_queue<pll, vector<pll>, greater<pll> >q;

     q.push(pll (,));// 距离 位置

     while(!q.empty())

     {

         pll temp = q.top(); q.pop();

         int x = temp.second, ss = temp.first;

         if(dis[x]!= ss)

            continue;

         for(int i = ; i < G[x].size(); i++)

         {

             int y = G[x][i].next, d = G[x][i].s;

             if( dis[y] > dis[x] + d)

             {

                 dis[y]= dis[x]+d;

                 q.push(pll (dis[y],y));

             }

         }

     }

 }

 void init(int n)

 {

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

         {

             dis[i] = INF;

             G[i].clear();

         }

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     int n, m;

     while(cin >> n >> m, n+m)

     {

         init(n);

         int x, y, d;

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

         {

             cin >> x >> y >> d;

             G[x].push_back(Node(y,d));

             G[y].push_back(Node(x,d));

         }

         dis[] = ;

         dijkstra();

         cout << dis[n] << endl;

     }

     return ;

 }