#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

class State{
public:
	int n,cost,r;

	State(int tn,int tcost,int tr){
		n = tn;
		cost = tcost;
		r = tr;
	}

	void show(){
		printf("[%d,%d,%d]\n",n,cost,r);
	}

	bool operator<(const State &st) const {
		return cost > st.cost;
	}
};

int t[101][101];
bool closed[101][11];

int main(void){
	int c,n,m,s,d;

	while(cin>>c>>n>>m>>s>>d && (c||n||m||s||d)){
		memset(t,0,sizeof(t));

		for(int i=0;i<m;i++){
			int from,to,cost;
			cin>>from>>to>>cost;
			t[from][to] = t[to][from] = cost;
		}

		priority_queue<State> open;
		memset(closed,0,sizeof(closed));
		open.push(State(s,0,c));

		int ans = -1;

		while(!open.empty()){
			State st = open.top(); open.pop();
			if(closed[st.n][st.r]) continue;
			closed[st.n][st.r] = true;

			if(st.n == d){
				ans = st.cost;
				break;
			}

			for(int i=1;i<=n;i++){
				if(t[st.n][i] > 0){
					open.push(State(i,st.cost+t[st.n][i],st.r));
					if(st.r > 0) open.push(State(i,st.cost+t[st.n][i]/2,st.r-1));
				}
			}
		}

		cout<<ans<<endl;
	}

	return 0;
}