#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<VI> VVI;
template<class T> T gcd( T a, T b ) {
	return !b ? a : gcd( b, a % b );
}
template<class T> T lcm( T a, T b ) {
	return a / gcd( a, b ) * b;
}
template<class T> string print_v( vector<T> v ) {
	OSS oss;
	for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end();
          ++it_i ) {
		oss << *it_i << ", ";
	}
	return oss.str();
}

typedef pair <int, int> II;
typedef set <II> SII;
const int NONE = -1;

typedef II NODE;
typedef priority_queue <NODE, vector<NODE>, greater<NODE> > QUEUE;

int solve( int n, VVI G ) {
    QUEUE Q;
    Q.push( NODE( 0, 0 ) );
    int MC[n];
    for ( int i = 0; i < n; ++ i )
        MC[i] = INT_MAX;
    MC[0] = 0;

    while ( ! Q.empty() ) {
        NODE node = Q.top();
        Q.pop();
        int step = node.first;
        int cur = node.second;

        if ( cur == n - 1 ) return step;
        
        for ( int i = 0; i < n; ++ i ) {
            if ( G[cur][i] == NONE ) continue;
            int nstep = step + G[cur][i];
            if ( nstep >= MC[i] ) continue;
            MC[i] = nstep;
            Q.push( II( nstep, i ) );
        }
    }

    return -1;
}

int main() {
    int n, m;
    while ( cin >> n >> m && n ) {
        int G[n][n];
        for ( int i = 0; i < n; ++ i )
            for ( int j = 0; j < n; ++ j )
                G[i][j] = NONE;
        
        for ( int i = 0; i < m; ++ i ) {
            int a, b, c;
            cin >> a >> b >> c;
            a --;
            b --;
            if ( G[a][b] == NONE ) G[a][b] = c;
            G[a][b] = min( G[a][b], c );
            if ( G[b][a] == NONE ) G[b][a] = c;
            G[b][a] = min( G[b][a], c );
        }

        bool F[n][n];
        for ( int i = 0; i < n; ++ i )
            for ( int j = 0; j < n; ++ j )
                F[i][j] = false;
        for ( int i = 0; i < n; ++ i )
            for ( int j = 0; j < n; ++ j )
                for ( int k = 0; k < n; ++ k )
                    if ( G[i][j] != NONE && G[j][k] != NONE )
                        F[i][k] = true;
        
        SII S;
        for ( int i = 0; i < n; ++ i )
            for ( int j = i + 1; j < n; ++ j )
                if ( F[i][j] )
                    S.insert( II( i, j ) );
        S.insert( II( 0, 0 ) );

        int res = INT_MAX;
        for ( SII::iterator it_i = S.begin(); it_i != S.end(); ++ it_i ) {
            int T[n][n];
            for ( int i = 0; i < n; ++ i )
                for ( int j = 0; j < n; ++ j )
                    T[i][j] = G[i][j];
            II e = *it_i;
            T[e.first][e.second] = T[e.second][e.first] = 0;
            VVI VT( n, VI( n ) );
            for ( int i = 0; i < n; ++ i )
                for ( int j = 0; j < n; ++ j )
                    VT[i][j] = T[i][j];
            res = min( res, solve( n, VT ) );
        }

        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1108