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

#define rep(i,a) for(int i = 0 ; i < a ; i ++)
#define loop(i,a,b) for(int i = a ; i < b ; i ++)
typedef pair<int,int> pii;

int C,N,M,S,D;
int pass[200][200], d[200][200], used[200][20];

int min(int a,int b){
	return (a>b?b:a);
}

int dijkstra(int s,int V){
 	rep(i,200)rep(j,200){	// clean 
 		d[i][j] = (1<<30);
 		used[i][j] = false;
 	}   
 	d[S][C] = 0;

 	while(true){	// search loop
 		int v = -1, w = -1;	
 		rep(u,N){	// loop ever node
 			rep(i,C+1){
 				if( !used[u][i] && (v==-1 || d[u][i] < d[v][w] ))
 					v=u,w=i;
 			}
 		}

 		if(v == -1)break;	// couldn't access to D node
 		used[v][w] = true;

 		rep(u,N){
 			d[u][w] = min(d[u][w] , d[v][w] + pass[v][u]);
 			if(w-1 >= 0 && pass[v][u] != (1<<30)){
 				d[u][w-1] = min(d[u][w-1],d[v][w] + pass[v][u]/2.0);
 			}
 		}
 	}
 	int ret = (1<<30);
 	rep(i,C+1)ret = min(ret,d[D][i]);
 	return ret;

}

int main(void){
	while(cin>>C>>N>>M>>S>>D,C+N+M+S+D){
		--S,--D;
		rep(i,200){
			rep(j,200)pass[i][j] = (1<<30);
			pass[i][i] = 0;
		}
		while(M--){
			int a,b,c;
			cin>>a>>b>>c;
			--a,--b;
			pass[a][b] = pass[b][a] = c;
		}
		cout<<dijkstra(S,D)<<endl;;
	}
	

}