Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

const INF = 0x7FFFFFFF

var pass [][]int

func main() {
	for scanner.Scan() {
		pass = make([][]int, 200)
		for i := range pass {
			pass[i] = make([]int, 200)
		}
		buf := strings.Split(scanner.Text(), " ")
		c, _ := strconv.Atoi(buf[0])
		n, _ := strconv.Atoi(buf[1])
		m, _ := strconv.Atoi(buf[2])
		s, _ := strconv.Atoi(buf[3])
		d, _ := strconv.Atoi(buf[4])
		if c == 0 && n == 0 && m == 0 && s == 0 && d == 0 {
			break
		}
		s--
		d--
		for i := 0; i < 200; i++ {
			for j := 0; j < 200; j++ {
				pass[i][j] = INF
			}
		}
		for i := 0; i < 200; i++ {
			pass[i][i] = 0
		}
		for i := 0; i < m; i++ {
			scanner.Scan()
			buf_ := strings.Split(scanner.Text(), " ")
			a, _ := strconv.Atoi(buf_[0])
			b, _ := strconv.Atoi(buf_[1])
			f, _ := strconv.Atoi(buf_[2])
			a--
			b--
			pass[a][b] = f
			pass[b][a] = f
		}
		fmt.Println(dijkstra(s, d, c, n))
	}
}

func dijkstra(s, g, c, n int) float64 {
	d := make([][]float64, 200)
	used := make([][]bool, 200)
	for i := 0; i < 200; i++ {
		d[i] = make([]float64, 20)
		used[i] = make([]bool, 20)
	}
	for i := range d {
		for j := range d[i] {
			d[i][j] = INF
		}
	}
	d[s][c] = 0
	for {
		v := -1
		w := -1
		for u := 0; u < n; u++ {
			for i := 0; i < c+1; i++ {
				if !used[u][i] && (v == -1 || d[u][i] < d[v][w]) {
					v = u
					w = i
				}
			}
		}
		if v == -1 {
			break
		}
		used[v][w] = true
		for u := 0; u < n; u++ {
			d[u][w] = math.Min(d[u][w], d[v][w]+float64(pass[v][u]))
			if w-1 >= 0 && pass[v][u] != INF {
				d[u][w-1] = math.Min(d[u][w-1], d[v][w]+(float64(pass[v][u]/2.0)))
			}
		}
	}
	ret := float64(INF)
	for i := 0; i < c+1; i++ {
		ret = math.Min(ret, d[g][i])
	}
	return ret
}

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()

Python: from heapq import heappush, heappop
INF = 10 ** 20

while True:
  c, n, m, s, d = map(int, input().split())
  s -= 1
  d -= 1
  if c == 0:
    break
  edges = [[] for _ in range(n * (c + 1))]
  for _ in range(m):
    a, b, f = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(c + 1):
      edges[a + i * n].append((b + i * n, f))
      edges[b + i * n].append((a + i * n, f))
      if i != c:
        edges[a + i * n].append((b + (i + 1) * n, f // 2))
        edges[b + i * n].append((a + (i + 1) * n, f // 2))
  for i in range(c):
    edges[d + i * n].append((d + (i + 1) * n, 0))

  cost = [INF] * (n * (c + 1))
  que = []
  heappush(que, (0, s))
  while que:
    total, point = heappop(que)
    for to, fee in edges[point]:
      if cost[to] > total + fee:
        cost[to] = total + fee
        heappush(que, (total + fee, to))
  print(cost[d + n * c])