#include <cstdio>
#include <utility>
#include <queue>
#include <algorithm>
#define INF (1<<27)
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int> _P; //point chicket
typedef pair<int,_P> P; //cost _P
struct Edge {
	int to,cost;
	Edge(int _to,int _cost) {to=_to,cost=_cost;}
};
int dist[11][100];
vector<Edge> edges[100];
int main() {
	int c,n,m,s,d;
	while(scanf("%d %d %d %d %d",&c,&n,&m,&s,&d),c) {
		rep(i,n) edges[i].clear();
		rep(i,c+1) rep(j,n) dist[i][j]=INF;
		rep(i,m) {
			int a,b,f;
			scanf("%d %d %d",&a,&b,&f);
			edges[a-1].push_back(Edge(b-1,f));
			edges[b-1].push_back(Edge(a-1,f));
		}
		priority_queue<P,vector<P>,greater<P> > Q;
		Q.push(P(0,_P(s-1,c)));
		dist[c][s-1]=0;
		while(!Q.empty()) {
			P p=Q.top(); Q.pop();
			_P _p=p.second;
			if(dist[_p.second][_p.first]<p.first) continue;
			rep(i,edges[_p.first].size()) {
				if(dist[_p.second][edges[_p.first][i].to]>(p.first+edges[_p.first][i].cost)) {
					dist[_p.second][edges[_p.first][i].to]=(p.first+edges[_p.first][i].cost);
					Q.push(P(p.first+edges[_p.first][i].cost,_P(edges[_p.first][i].to,_p.second)));
				}
				if(_p.second>0&&(dist[_p.second-1][edges[_p.first][i].to]>(p.first+edges[_p.first][i].cost/2))) {
					dist[_p.second-1][edges[_p.first][i].to]=(p.first+edges[_p.first][i].cost/2);
					Q.push(P(p.first+edges[_p.first][i].cost/2,_P(edges[_p.first][i].to,_p.second-1)));
				}
			}
		}
		int sum=1<<30;
		rep(i,c+1)if(sum>dist[i][d-1])sum=dist[i][d-1];
		printf("%d\n",sum);
	}
}