#include <queue>

#include <climits>

#include <cstdio>

#include <vector>

#include <utility>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

typedef pair<int, int> PII;

const int MAX_N =  + ;

const int MAX_M =  + ;

int u[MAX_N], v[MAX_N], w[MAX_N];

bool done[MAX_N];

int d[MAX_N];

vector<PII> G[MAX_N];

void Dijkstra(int n)

{

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

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

        d[i] = (i ==  ?  : INT_MAX);

    memset(done, NULL, sizeof(done));

    q.push(make_pair(d[], ));

    while (!q.empty())

    {

        PII x = q.top();

        q.pop();

        int u = x.second;

        if (done[u]) continue;

        done[u] = true;

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

        {

            int v = G[u][i].first;

            int w = G[u][i].second;

            if (d[v] > d[u] + w)

            {

                d[v] = d[u] + w;

                q.push(make_pair(d[v], v));

            }

        }

    }

}

int main()

{

    int N, M;

    while (scanf("%d %d", &N, &M) != EOF && N && M)

    {

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

        {

            scanf("%d %d %d", &u[e], &v[e], &w[e]);

            G[u[e]].push_back(make_pair(v[e], w[e]));

            G[v[e]].push_back(make_pair(u[e], w[e]));

        }

        Dijkstra(N);

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

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

            G[i].clear();

    }

    return ;

}