#include <cstdio>
#include <vector>

using namespace std;

class Edge{
public:
	int from,to,cost;
	void Swap(){
		int a = from;
		from = to;
		to = a;
	}
};

vector<Edge> edges;

const int INF = 999999999;

int solve(int s,int g,int c){
	int d[101][11];
	bool flag[101][11];
	for(int i=0;i<101;i++){
		for(int j=0;j<11;j++){
			d[i][j] = INF;
			flag[i][j] = false;
		}
	}
	d[s][c] = 0;
	
	vector<Edge>::iterator eit;
	
	while(1){
		int no,nc;
		bool f = true;
		for(int i=0;i<101;i++){
			for(int j=c;j>=0;j--){
				if(d[i][j] != INF && flag[i][j] == false){
					if(f){
						no = i;
						nc = j;
					}else if(d[no][nc] > d[i][j]){
						no = i;
						nc = j;
					}
					f = false;
				}
			}
		}
		if(f){break;}
		flag[no][nc] = true;
		for(eit = edges.begin();eit != edges.end(); eit++){
			if(eit->from == no){
				if(d[eit->to][nc] > d[eit->from][nc] + eit->cost){
					d[eit->to][nc] = d[eit->from][nc] + eit->cost;
				}
				if(nc > 0){
					if(d[eit->to][nc - 1] > d[eit->from][nc] + eit->cost / 2){
						d[eit->to][nc - 1] = d[eit->from][nc] + eit->cost / 2;
					}
				}
			}
		}
	}
	int ans = INF;
	for(int i=0;i<c;i++){
		if(d[g][i] < ans){
			ans = d[g][i];
		}
	}
	return ans;
}

int main(){
	int c,n,m,s,d;
	int a,b,f;
	while(1){
		scanf("%d %d %d %d %d",&c,&n,&m,&s,&d);
		if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0){
			break;
		}
		edges.clear();
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&a,&b,&f);
			Edge e;
			e.from = a;
			e.to = b;
			e.cost = f;
			edges.push_back(e);
			e.Swap();
			edges.push_back(e);
		}
		printf("%d\n",solve(s,d,c));
	}
	return 0;
}