#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
const int inf=1e9;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main(){
  int n,m;
  while(cin>>n>>m,n+m){
    vvi cost(3*n,vi(3*n,inf));
    rep(i,m){
      int a,b,c;
      cin>>a>>b>>c;
      a--;b--;
      cost[a][b]=cost[b][a]=c;
      cost[2*n+a][2*n+b]=cost[2*n+b][2*n+a]=c;
      cost[a][n+b]=cost[n+a][2*n+b]=0;
      cost[b][n+a]=cost[n+b][2*n+a]=0;
    }
    vi used(3*n),d(3*n,inf);
    d[0]=0;
    while(1){
      int v=-1;
      rep(i,3*n)if(used[i]==0&&(v==-1||d[v]>d[i]))v=i;
      if(v==-1)break;
      used[v]=1;
      rep(i,3*n)d[i]=min(d[i],d[v]+cost[v][i]);
    }
    cout<<min(d[n-1],d[3*n-1])<<endl;
  }
}