#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_N = int(3e5) + 5;
const double EPS = 1e-8;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
string dir = "RDLU";
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define SORT(v) sort((v).begin(), (v), end())
#define SORTR(v) sort((v).rbegin(), (v), rend())
#define ALL(v) (v).begin(), (v).end()

int main() {
    while (1) {
        int n, m, d[105][105]{};
        vector<int> g[105];
        cin >> n >> m;
        if(n==0)break;
        REP(i, n) fill(d[i], d[i] + n, IINF / 2);
        REP(i,n) d[i][i] = 0;
        REP(i, m) {
            int a, b, c;
            cin >> a >> b >> c;
            a--;
            b--;
            d[a][b] = c;
            d[b][a] = c;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        REP(k, n) REP(i, n) REP(j, n) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        int ans = d[0][n-1];
        REP(k, n) REP(j, g[k].size()) REP(i, j) {
            ans = min(ans,d[0][g[k][i]]+d[g[k][j]][n-1]);
            ans = min(ans,d[0][g[k][j]]+d[g[k][i]][n-1]);
        }
        cout << ans << endl;
    }
    return 0;
}

