#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct NODE{
	int to,cost,ticket;
	NODE(int to,int cost,int ticket) : to(to) , cost(cost) , ticket(ticket) {}
	NODE(){}
};


bool operator < (const NODE &a,const NODE &b){
	return a.cost > b.cost;
}

int main(){
	int c,n,m,s,d;
	while(cin >> c >> n >> m >> s >> d && n){
		s--,d--;
		vector<NODE> e[100];
		for(int i = 0 ; i < m ; i++){
			int a,b,f;
			cin >> a >> b >> f;
			a--,b--;
			e[a].push_back(NODE(b,f,-1));
			e[b].push_back(NODE(a,f,-1));
		}
		int done[110][15] = {};
		priority_queue<NODE> Q;
		Q.push(NODE(s,0,c));
		while(Q.size()){
			NODE q = Q.top(); Q.pop();
			if( done[q.to][q.ticket]++ ) continue;
			else done[q.to][q.ticket] = true;
			if( q.to == d){
				cout << q.cost << endl;
				break;
			}
			for(int i = 0 ; i < e[q.to].size() ; i++){
				Q.push(NODE(e[q.to][i].to,q.cost+e[q.to][i].cost,q.ticket));
				if( q.ticket ) Q.push(NODE(e[q.to][i].to,q.cost+e[q.to][i].cost/2,q.ticket-1));
			}
		}
	}
}