#include<iostream>

#include<queue>

#include<cstring>

#define INF 0x3f3f3f3f

using namespace std;

int main()

{

    int n,m,x,y,val,now,map[][],dis[],vis[];

    while(cin>>n>>m)

    {

        queue<int>q;

        if(n==&&m==)

        break;

        memset(vis,,sizeof(vis));

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

        {

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

            {

                if(i==j)

                map[i][j]=;

                else

                map[i][j]=INF;

            }

        }

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

        {

            cin>>x>>y>>val;

            map[x-][y-]=val;

            map[y-][x-]=val;

        }

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

        {

            dis[i]=INF;

        }

        dis[]=;

        vis[]=;

        q.push();

        while(!q.empty())

        {

            now=q.front();

            q.pop();

            vis[now]=;

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

            {

                if(dis[i]>dis[now]+map[now][i])

                {

                    dis[i]=dis[now]+map[now][i];

                    if(vis[i]==)

                    {

                        q.push(i);

                        vis[i]=;

                    }

                }

            }

        }

        cout<<dis[n-]<<endl;

    }

}