#include <iostream>
#include <cstdio>
#include <queue>
#include <cassert>

using namespace std;

int N, M;

struct Edge {
  int dst;
  int cost;
  Edge(int dst, int cost): dst(dst), cost(cost) {}
};

vector<Edge> Graph[200];

const int MAX = 10000000;
int min_cost[200][2];

void init() {
  for (int i = 0; i < 200; i++) {
    Graph[i].clear();
  }
  for (int i = 0; i < 200; i++) {
    for (int j = 0; j < 2; j++) {
      min_cost[i][j] = MAX;
    }
  }
}

struct State {
  int current;
  int used;
  int cost;
  State(int current, int used, int cost) : current(current), used(used), cost(cost) {}
  bool operator<(const State & rhs) const {
    return cost > rhs.cost;
  }
};


void solve() {
  priority_queue<State> Q;
  Q.push(State(0, 0, 0));

  while (!Q.empty()) {
    State c = Q.top();

    Q.pop();

    int cur = c.current;
    int used = c.used;
    int cost = c.cost;
    if (cur == N - 1) {
      cout << cost << endl;
      return;
    }
    if (min_cost[cur][used] < c.cost) {
      continue;
    }
    min_cost[cur][used] = c.cost;

    for (int i = 0; i < Graph[cur].size(); i++) {
      int dst = Graph[cur][i].dst;
      int dcost = Graph[cur][i].cost;
      if (min_cost[dst][used] > cost + dcost) {
        min_cost[dst][used] = cost + dcost;
        Q.push(State(dst, used, cost + dcost));
      }
      if (!used) {
        for (int j = 0; j < Graph[dst].size(); j++) {
          int next_dst = Graph[dst][j].dst;
          if (min_cost[next_dst][1] > cost) {
            min_cost[next_dst][1] = cost;
            Q.push(State(next_dst, 1, cost));
          }
        }
      }
    }
  }
  assert(false);
}

int main() {
  while (true) {
    cin >> N >> M;
    if (N == 0 && M == 0) {
      return 0;
    }
    init();
    for (int i = 0; i < M; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      a--, b--;
      Graph[a].push_back(Edge(b, c));
      Graph[b].push_back(Edge(a, c));
    }
    solve();
  }
}