/*

Dijkstra的算法思想：

在所有没有访问过的结点中选出dis(s,x)值最小的x

对从x出发的所有边(x,y),更新

dis(s,y)=min(dis(s,y),dis(s,x)+dis(x,y))

*/

#include <iostream>

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

const int Ni = ;

const int INF = <<;

struct node

{

    int x,d;

    node() {}

    node(int a,int b)

    {

        x=a;

        d=b;

    }

    bool operator < (const node & a) const

    {

        if(d==a.d) return x<a.x;

        else return d > a.d;

    }

};

vector<node> eg[Ni];

int dis[Ni],n;

void Dijkstra(int s)

{

    int i;

    for(i=; i<=n; i++) dis[i]=INF;

    dis[s]=;

//用优先队列优化

    priority_queue<node> q;

    q.push(node(s,dis[s]));

    while(!q.empty())

    {

        node x=q.top();

        q.pop();

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

        {

            node y=eg[x.x][i];

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

            {

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

                q.push(node(y.x,dis[y.x]));

            }

        }

    }

}

int main()

{

    int a,b,d,m;

    while(scanf("%d%d",&n,&m),n+m)

    {

        for(int i=; i<=n; i++) eg[i].clear();

        while(m--)

        {

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

            eg[a].push_back(node(b,d));

            eg[b].push_back(node(a,d));

        }

        Dijkstra();

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

    }

    return ;

}

/*

6 6

1 2 2

3 2 4

1 4 5

2 5 2

3 6 3

5 6 3

*/