#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
int main(){
	int c,n,m,s,d;
	while(cin>>c>>n>>m>>s>>d,n){
		s--;d--;
		int cost[110][110];
		rep(i,110)rep(j,110)cost[i][j]=inf;
		while(m--){
			int a,b,e;
			cin>>a>>b>>e;
			a--;b--;
			cost[a][b]=cost[b][a]=e;
		}
		int dp[110][11];
		int used[110]={0};
		rep(i,110)rep(j,11)dp[i][j]=inf;
		rep(i,11)dp[s][i]=0;
		while(1){
			int v=-1;
			rep(i,n)if(!used[i]&&(v==-1||dp[v][0]>dp[i][0]))v=i;
			if(v==-1)break;
			used[v]=true;
			rep(i,n)for(int j=c;j>=0;j--){
				dp[i][j]=min(dp[i][j],dp[v][j]+cost[v][i]);
				dp[i][j+1]=min(dp[i][j+1],dp[v][j]+cost[v][i]/2);
			}
		//rep(i,6){rep(j,3)cout<<" "<<dp[i][j];cout<<endl;}
		//cout<<endl;
		}
		//rep(i,6){rep(j,3)cout<<" "<<dp[i][j];cout<<endl;}
		cout<<dp[d][c]<<endl;
	}
}