#include<iostream>

#include<cstdio>

using namespace std;

const int INF=10e7;

const int MAXN=1010;

int k,minn;

int cost[MAXN][MAXN];

int lowcost[MAXN];

bool vis[MAXN];

void dij(int n,int start)

{

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

    {

        lowcost[i]=INF;vis[i]=0;

    }

    lowcost[start]=0;

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

    {

        k=-1,minn=INF;

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

        {

            if(!vis[i]&&lowcost[i]<minn)

                {minn=lowcost[i];k=i;}

        }

        if(k==-1) break;

        vis[k]=1;

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

        {

            if(!vis[i]&&cost[k][i]>=0&&lowcost[k]+cost[k][i]<lowcost[i])

            {

                lowcost[i]=lowcost[k]+cost[k][i];

            }

        }

    }

}

int main()

{

    int n,m,a,b,c;

    while(scanf("%d%d",&n,&m)&&n!=0&&m!=0)

    {

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

        {

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

            {

                if(i==j) cost[i][j]=0;

                else cost[i][j]=INF;

            }

        }

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

        {

            scanf("%d%d%d",&a,&b,&c);

            cost[a][b]=cost[b][a]=c;

        }

        dij(n,1);

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

    }

    return 0;

}