#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e8
#define EPS 1e-9

#define rep2(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) rep2(i,0,n)
#define ll long long
#define P pair<int,int>
#define pb push_back

struct edge{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};

int c,n,m,s,D,d[1100];
vector<edge> g[1100];

void dijkstra(int s){
	priority_queue<P,vector<P>,greater<P> > q;
	fill(d,d+c*100+n,INF);
	d[s]=0;
	q.push(P(0,s));
	while(!q.empty()){
		P p=q.top();q.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		rep(i,g[v].size()){
			edge e=g[v][i];
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				q.push(P(d[e.to],e.to));
			}
		}
	}
}

int main(){
	while(cin>>c>>n>>m>>s>>D&&n){
		s--;D--;
		rep(i,c*100+n)g[i].clear();
		rep(i,m){
			int a,b,f;
			cin>>a>>b>>f;
			a--;b--;
			rep(j,c+1){
				g[j*100+a].pb(edge(j*100+b,f));
				g[j*100+b].pb(edge(j*100+a,f));
			}
			rep(j,c){
				g[(j+1)*100+a].pb(edge(j*100+b,f/2));
				g[(j+1)*100+b].pb(edge(j*100+a,f/2));
			}
		}
		dijkstra(c*100+s);
		int ans=INF;
		rep(i,c+1)ans=min(ans,d[i*100+D]);
		cout<<ans<<endl;
	}
}