### constant

MAX_INT = (1 << 31) - 1

### main

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

  sn -= 1
  dn -= 1

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

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

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

  dists = n.times.map{[MAX_INT] * (c + 1)}
  dists[sn][c] = 0
  visited = n.times.map{[false] * (c + 1)}
  visited[sn][c] = true
  q = [[sn, c]]

  while ! q.empty?
    nd0, c0 = q.shift
    next if nd0 == dn

    for nd1 in nbrs[nd0]
      e = edges[nd0][nd1]
      he = e / 2
      if dists[nd1][c0] > dists[nd0][c0] + e
        dists[nd1][c0] = dists[nd0][c0] + e
        q << [nd1, c0]
      end
      if c0 > 0 && dists[nd1][c0 - 1] > dists[nd0][c0] + he
        dists[nd1][c0 - 1] = dists[nd0][c0] + he
        q << [nd1, c0 - 1]
      end
    end
  end

  puts dists[dn].min
end