require 'set'
loop do
    c, n, m, s, d = gets.split.map(&:to_i)
    break if c == 0
    g = {}
    (1..n).each {|i| g[i] = {}}
    m.times do
        a, b, f = gets.split.map(&:to_i)
        g[a][b] = f
        g[b][a] = f
    end
    start_node = [s, c]
    nodes = Set[start_node]
    cost = Hash.new(Float::INFINITY)
    cost[start_node] = 0
    reached = Set.new
    loop do
        u = nodes.min_by {|v| cost[v]}
        nodes.delete(u)
        reached << u
        i, k = u
        if i == d
            puts cost[u]
            break
        end
        g[i].each do |j, f|
            if k > 0
                v = [j, k - 1]
                if !reached.include?(v)
                    cost[v] = cost[u] + f / 2 if cost[v] > cost[u] + f / 2
                    nodes << v
                end
            end
            v = [j, k]
            if !reached.include?(v)
                cost[v] = cost[u] + f if cost[v] > cost[u] + f
                nodes << v
            end
        end
    end
end

