Go: package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	NowPosition          int
	DiscountTicketTCount int
	Amount               int
}

type PriorityQueueNode []*Node

func (pq PriorityQueueNode) Len() int {
	return len(pq)
}

func (pq PriorityQueueNode) Less(i, j int) bool {
	return pq[i].Amount < pq[j].Amount
}

func (pq PriorityQueueNode) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueueNode) Push(node interface{}) {
	*pq = append(*pq, node.(*Node))
}

func (pq *PriorityQueueNode) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

type Point struct {
	NextPoint int
	Fee       int
}

func main() {
	var c, n, m, s, d int
	var a, b, f int

	for {
		fmt.Scan(&c, &n, &m, &s, &d)
		if c == 0 && n == 0 && m == 0 && s == 0 && d == 0 {
			break
		}
		s--
		d--
		pointMap := make([][]Point, n)
		for i := 0; i < n; i++ {
			pointMap[i] = make([]Point, 0)
		}
		for i := 0; i < m; i++ {
			fmt.Scan(&a, &b, &f)
			a--
			b--
			pointMap[a] = append(pointMap[a], Point{NextPoint: b, Fee: f})
			pointMap[b] = append(pointMap[b], Point{NextPoint: a, Fee: f})
		}
		pq := make(PriorityQueueNode, 0)
		start := Node{NowPosition: s, DiscountTicketTCount: c, Amount: 0}
		heap.Push(&pq, &start)
		for len(pq) != 0 {
			now := heap.Pop(&pq).(*Node)
			if now.NowPosition == d {
				fmt.Println(now.Amount)
				break
			}
			for _, v := range pointMap[now.NowPosition] {
				next := &Node{v.NextPoint, now.DiscountTicketTCount, now.Amount + v.Fee}
				heap.Push(&pq, next)
				if now.DiscountTicketTCount > 0 {
					next = &Node{v.NextPoint, now.DiscountTicketTCount - 1, now.Amount + v.Fee/2}
					heap.Push(&pq, next)
				}
			}
		}
	}
}

Python: from heapq import *

while True:
    #input c,n,m,s,d & creating G
    #G[to,cost]
    c,n,m,s,d=map(int,input().split())
    
    if c==n==m==s==d==0:
        break
    
    G=[[]]
    for i in range(n):
        G.append([])
    for i in range(m):
        a,b,f=map(int,input().split())
        G[a].append([b,f])
        G[b].append([a,f])

    #creating dp[]
    INF=1e8
    dp=[]
    for i in range(c+1):
        temp=[INF for j in range(n+1)]
        dp.append(temp)

    def dijkstra(s,c):
        que=[]
        dp[0][s]=0
        heappush(que,[dp[c][s],s])

        while len(que)!=0:
            p=heappop(que)
            v=p[1] #v is the current location
            if(dp[c][v]<p[0]):
                continue
            for i in range(len(G[v])):
                e=G[v][i]
                Min=dp[c][v]+e[1] if c==0 else min(dp[c-1][v]+e[1]/2,dp[c][v]+e[1])
                if(dp[c][e[0]]>Min):
                    dp[c][e[0]]=Min
                    heappush(que,[dp[c][e[0]],e[0]])

    for i in range(c+1):
        dijkstra(s,i)
    print(int(dp[c][d]))

Python: """ Created by Jieyi on 10/31/16. """
import io
import sys
import heapq

# Simulate the redirect stdin.
from collections import defaultdict

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def input_data():
    while True:
        tickets, vertices, edges, start, end = map(int, input().split())
        if 0 == tickets + vertices + edges + start + end:
            break

        shortest_path = [[sys.maxsize for _ in range(vertices + 1)] for _ in range(tickets + 1)]
        for i in range(tickets + 1):
            shortest_path[i][start] = 0
        g = defaultdict(list)
        h = []
        # Generate a map.
        for _ in range(edges):
            i, j, fare = map(int, input().split())
            g[i].append((j, fare))
            g[j].append((i, fare))
        # (price, vertices, remainder ticket)
        heapq.heappush(h, (0, start, tickets))

        while True:
            if 0 == len(h):
                break
            ori_price, vertex, remain_ticket = heapq.heappop(h)
            for v, price in g[vertex]:
                if shortest_path[remain_ticket][v] > ori_price + price:
                    shortest_path[remain_ticket][v] = min(shortest_path[remain_ticket][v], ori_price + price)
                    heapq.heappush(h, (shortest_path[remain_ticket][v], v, remain_ticket))
                if remain_ticket and shortest_path[remain_ticket - 1][v] > ori_price + int(price / 2):
                    shortest_path[remain_ticket - 1][v] = min(shortest_path[remain_ticket - 1][v], ori_price + int(price / 2))
                    heapq.heappush(h, (shortest_path[remain_ticket - 1][v], v, remain_ticket - 1))

        print(shortest_path[0][end])


def main():
    input_data()


if __name__ == '__main__':
    main()

Python: INF = 10000000

def bf(es, dist, c, s, d):
    dist[s][0] = 0

    isUpdated = True
    while isUpdated:
        isUpdated = False
        for e in es:
            a, b, f = e
            for i in range(c+1):
                if dist[a][i] != INF and dist[a][i] + f < dist[b][i]:
                    dist[b][i] = dist[a][i] + f
                    isUpdated = True
                if dist[a][i] != INF and (i+1) <= c and dist[a][i] + f / 2 < dist[b][i+1]:
                    dist[b][i+1] = dist[a][i] + int(f / 2)
                    isUpdated = True
    
    return min(dist[d])

if __name__ == '__main__':
    while True:
        c, n, m, s, d = map(int, input().split())
        if c == 0:
            break

        s -= 1
        d -= 1
        es = []
        dist = [[INF for _ in range(c+1)] for __ in range(n)] # dist[i][j]: ???i?????§????????????j????????£??????????????????
        for _ in range(m):
            a, b, f = map(int, input().split())
            a -= 1
            b -= 1
            es.append([a, b, f])
            es.append([b, a, f])

        print(bf(es, dist, c, s, d))

Python: """ Created by Jieyi on 10/31/16. """
import io
import sys
import heapq

# Simulate the redirect stdin.
from collections import defaultdict

if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def input_data():
    while True:
        tickets, vertices, edges, start, end = map(int, input().split())
        if 0 == tickets + vertices + edges + start + end:
            break

        # shortest_path = [[sys.maxsize for _ in range(vertices)] for _ in range(tickets)]
        shortest_path = [sys.maxsize for _ in range(vertices)]
        g = defaultdict(list)
        h = []
        # Generate a map.
        for _ in range(edges):
            i, j, fare = map(int, input().split())
            g[i].append((j, fare))
            g[j].append((i, fare))
        # (price, vertices, remainder ticket)
        heapq.heappush(h, (0, start, tickets))

        while True:
            if 0 == len(h):
                break
            head = heapq.heappop(h)
            for v, price in g[head[1]]:
                if shortest_path[v - 1] > head[0] + price:
                    shortest_path[v - 1] = min(shortest_path[v - 1], head[0] + price)
                    heapq.heappush(h, (shortest_path[v - 1], v, head[2]))
                if 0 != head[2]:
                    if shortest_path[v - 1] > head[0] + int(price / 2):
                        shortest_path[v - 1] = min(shortest_path[v - 1], head[0] + int(price / 2))
                        heapq.heappush(h, (shortest_path[v - 1], v, head[2] - 1))

        print(shortest_path[end - 1])


def main():
    input_data()


if __name__ == '__main__':
    main()