class Node
  attr_accessor :town,:ticket,:cost
  def initialize(town, ticket, cost)
    @town, @ticket, @cost = town, ticket, cost
  end
  include Comparable
  def <=>(n)
    @cost!=n.cost ? @cost<=>n.cost : (@ticket!=n.ticket ? -(@ticket<=>n.ticket) : @town<=>n.town)
  end
  def copy
    Node.new(@town, @ticket, @cost)
  end
end

def Dijkstra(adjacentMatrix, s, d, c)
  adj = adjacentMatrix.map(&:dup)
  n = adj.size
  cost = 5000000
  visited = Array.new(n){Array.new(c)}
  q = Array.new.push(Node.new(s, c, 0))
  until q.empty? do
    now = q.sort!.shift
    if now.town == d
      cost = [cost, now.cost].min
      next
    end
    next if visited[now.town][now.ticket]
    visited[now.town][now.ticket] = true
    n.times do |nextTown|
      next unless adj[now.town][nextTown]
      to = now.copy
      to.town = nextTown
      to.cost += adj[now.town][to.town]
      q.push(to)
      next if to.ticket == 0
      to.ticket -= 1
      to.cost -= adj[now.town][to.town]/2
      q.push(to)
    end
  end
  cost
end

until (c,n,m,s,d=gets.split.map(&:to_i)).all?(&:zero?) do
  adjacent = Array.new(n) {Array.new(n)}
  m.times do
    a, b, f = gets.split.map(&:to_i)
    a -= 1
    b -= 1
    adjacent[a][b] = adjacent[b][a] = f
  end
  p Dijkstra(adjacent, s-1, d-1, c)
end