#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < k; i++)
typedef long long ll;
typedef unsigned long long ull;

struct edge{
	int to,cost,dis;
};

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

int main(){
	int c,n,m,s,g;
	while(scanf("%d%d%d%d%d",&c,&n,&m,&s,&g),n){
		int ans = 0;
		s--,g--;
		vector<edge> G[128];
		int d[128][32]={{}};
		rep(i,m){
			int a,b,cst;
			scanf("%d%d%d",&a,&b,&cst);
			a--,b--;
			edge in;
			in = {b,cst,-1};
			G[a].push_back(in);
			in = {a,cst,-1};
			G[b].push_back(in);
		}
		priority_queue<edge> PQ;
		edge start = {s,0,c};
		PQ.push(start);
		while(!PQ.empty()){
			edge pq = PQ.top();
			PQ.pop();
			if(d[pq.to][pq.dis]){
				d[pq.to][pq.dis]++;
				continue;
			}
			d[pq.to][pq.dis] = true;
			if(pq.to == g){
				printf("%d\n",pq.cost);
				break;
			}
			rep(u,G[pq.to].size()){
				edge next = {G[pq.to][u].to,pq.cost+G[pq.to][u].cost,pq.dis};
				PQ.push(next);
				if(pq.dis){
					next = {G[pq.to][u].to,pq.cost+G[pq.to][u].cost/2,pq.dis-1};
					PQ.push(next);
				}
			}
		}
	}
	return 0;
}