#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cctype>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
#include <complex>
#include <utility>
#include <numeric>
using namespace std;
const int INF=1<<30;

struct edge{int to,cost;};
typedef pair<int,int> P;

int V;
vector<edge> G[100];
int d[11][100];
priority_queue<P, vector<P>, greater<P> > que;

void dijkstra(int s,int a){
	
	
	for(int i=0;i<V;i++)
		d[a][i]=INF;
	que.push(P(0,s));
	d[a][s]=0;
	
	while(!que.empty()){
		P p = que.top();que.pop();
		int v = p.second;
		if(d[a][v]<p.first)	continue;
		for(int i=0;i<G[v].size();i++){
			edge e = G[v][i];
			int Min = (a==0 ? d[a][v]+e.cost : min(d[a][v]+e.cost,d[a-1][v]+e.cost/2));
			if(d[a][e.to]>Min){
				d[a][e.to]=Min;
				que.push(P(d[a][e.to],e.to));
			}
		}
	}
}

int main(){
	
	int c,m,s,end;
	edge E;
	while(cin>>c>>V>>m>>s>>end,!(c==0&&V==0&&m==0&&s==0&&end==0)){
		for(int i=0;i<m;i++){
		int a,b,f;
		cin>>a>>b>>f;
		a--;
		b--;
		E.to=b;
		E.cost=f;
		G[a].push_back(E);
		E.to=a;
		G[b].push_back(E);
		}
	
	s--;
    end--;
	for(int i=0;i<=c;i++) dijkstra(s,i);
	
	cout<<d[c][end]<<endl;
	

		for(int i=0;i<100;i++)
		G[i].clear();
	}
	
}