### constant

MAX_INT = (1 << 30)

### main

while true
  n, m = gets.strip.split(' ').map{|s| s.to_i}
  break if n == 0 && m == 0

  edges = n.times.map{[]}
  nbrs = n.times.map{[]}

  m.times do
    a, b, c = gets.strip.split(' ').map{|s| s.to_i}
    a -= 1
    b -= 1

    edges[a][b] = edges[b][a] = c
    nbrs[a] << b
    nbrs[b] << a
  end

  start = 0
  goal = n - 1

  dists = n.times.map{[MAX_INT] * 3}
  used = n.times.map{[false] * 3}

  dists[start][2] = 0
  used[start][2] = true
  q = [[0, 2]]

  while ! q.empty?
    u = q.min{|a, b| dists[a[0]][a[1]] <=> dists[b[0]][b[1]]}
    q.delete(u)

    u0, u1 = u
    next if u0 == goal

    for v0 in nbrs[u0]
      if u1 != 1
        if dists[v0][u1] > dists[u0][u1] + edges[u0][v0]
          dists[v0][u1] = dists[u0][u1] + edges[u0][v0]
          if ! used[v0][u1]
            used[v0][u1] = true
            q << [v0, u1]
          end
        end
      end

      if u1 > 0
        if dists[v0][u1 - 1] > dists[u0][u1]
          dists[v0][u1 - 1] = dists[u0][u1]
          if ! used[v0][u1 - 1]
            used[v0][u1 - 1] = true
            q << [v0, u1 - 1]
          end
        end
      end
    end
  end

  puts [dists[goal][0], dists[goal][2]].min
end