Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = f;
		field[(b, a)] = f;
	visited = set()
	q = []
	heapq.heappush(q, (0, c, -1, s))
	while q:
		cost, rem, frm, pos = heapq.heappop(q)
		if pos == d and (rem == 0 or (c > n and rem == c - n)):
			print cost
			break
		visited.add((rem, pos))
		for i in xrange(1, n + 1):
			edge = (pos, i)
			if edge in field:
				next = (rem, i)
				if not next in visited:
					heapq.heappush(q, (cost + field[edge], rem, pos, i))
				if rem > 0:
					next = (rem - 1, pos)
					if not next in visited:
						heapq.heappush(q, (cost + field[edge] / 2, rem - 1, pos, i))

Fixed submission:
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			next = (rem, i)
			ncost = cost + field.get(edge, 0x7fffffff)
			if ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem, i))
				visited[next] = ncost
			next = (rem - 1, i)
			ncost = cost + field.get(edge, 0x7fffffff) / 2
			if rem > 0 and ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem - 1, i))
				visited[next] = ncost

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = f;
		field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			if edge in field:
				next = (rem, i)
				ncost = cost + field[edge]
				if not next in visited or visited[next] < ncost:
					heapq.heappush(q, (ncost, rem, i))
					visited[next] = ncost
				if rem > 0:
					next = (rem - 1, pos)
					ncost = cost + field[edge] / 2
					if not next in visited or visited[next] < ncost:
						heapq.heappush(q, (ncost, rem - 1, i))
						visited[next] = ncost

Fixed submission:
#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			next = (rem, i)
			ncost = cost + field.get(edge, 0x7fffffff)
			if ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem, i))
				visited[next] = ncost
			next = (rem - 1, i)
			ncost = cost + field.get(edge, 0x7fffffff) / 2
			if rem > 0 and ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem - 1, i))
				visited[next] = ncost