// Original C++ solution (slower):
//Solution for aoj:0212 Highway Express Bus

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

using namespace std;

typedef pair<int, int>P;

typedef pair < P, int > PP;

#define f first

#define s second



//struct S {

//	int cost, to, num;

//	S(int c, int t, int n) : cost(c), to(t), num(n){}

//	bool operator>(const S &s) const {

//		return cost > s.cost;

//	}

//};



const int INF = 1 << 29;

int c, n, m, s, d, ans;

int tocost[1000][100];

vector<P> town[1000];





void dijkstra(){

	priority_queue<PP, vector<PP>, greater<PP> > pq;

	pq.push({ { 0, s }, c });

	while (!pq.empty()){

		PP a = pq.top();

		pq.pop();

		for (int i = 0; i < town[a.f.s].size(); i++){

			int tt = town[a.f.s][i].f, cc = town[a.f.s][i].s;

			if (tocost[tt][a.s] > cc + a.f.f){

				tocost[tt][a.s] = cc + a.f.f;

				pq.push({ { cc + a.f.f, tt }, a.s });

			}

			if (a.s&&tocost[tt][a.s-1] > cc/2 + a.f.f){

				tocost[tt][a.s-1] = cc/2 + a.f.f;

				pq.push({ { cc / 2 + a.f.f, tt }, a.s - 1 });

			}

		}

	}

}

	int main(){

		while (cin >> c >> n >> m >> s >> d&&c&&n&&m&&s){

			for (int i = 0; i < 1000; i++)

				fill(tocost[i], tocost[i] + 100, INF);

			tocost[s][c] = 0;

			ans = INF;

			for (int i = 0; i < 1000; i++)

				town[i].clear();

			for (int i = 0; i < m; i++){

				int a, b, c;

				cin >> a >> b >> c;

				town[a].push_back({ b, c });

				town[b].push_back({ a, c });

			}

			dijkstra();

			for (int i = 0; i <= c; i++)

				ans = min(ans, tocost[d][i]);

			cout << ans << endl;

		}

		return 0;

	}

// Optimized solution to the same problem (faster):
//Solution for aoj:0212 Highway Express Bus

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<functional>

using namespace std;

typedef pair<int, int>P;

typedef pair < P, int > PP;

#define f first

#define s second



//struct S {

//	int cost, to, num;

//	S(int c, int t, int n) : cost(c), to(t), num(n){}

//	bool operator>(const S &s) const {

//		return cost > s.cost;

//	}

//};



const int INF = 1 << 29;

int c, n, m, s, d, ans;

int tocost[1000][11];

vector<P> town[1000];

priority_queue<PP, vector<PP>, greater<PP> > pq;





void dijkstra(){

	while (!pq.empty()){

		PP a = pq.top();

		pq.pop();

		for (int i = 0; i < town[a.f.s].size(); i++){

			int tt = town[a.f.s][i].f, cc = town[a.f.s][i].s;

			if (tocost[tt][a.s] > cc + a.f.f){

				tocost[tt][a.s] = cc + a.f.f;

				pq.push({ { cc + a.f.f, tt }, a.s });

			}

			if (a.s&&tocost[tt][a.s-1] > cc/2 + a.f.f){

				tocost[tt][a.s-1] = cc/2 + a.f.f;

				pq.push({ { cc / 2 + a.f.f, tt }, a.s - 1 });

			}

		}

	}

}

	int main(){

		while (cin >> c >> n >> m >> s >> d&&c&&n&&m&&s){

			for (int i = 0; i < 1000; i++)

				fill(tocost[i], tocost[i] + 11, INF);

			tocost[s][c] = 0;

			ans = INF;

			while (pq.size())

				pq.pop();

			for (int i = 0; i < 1000; i++)

				town[i].clear();

			for (int i = 0; i < m; i++){

				int a, b, c;

				cin >> a >> b >> c;

				town[a].push_back({ b, c });

				town[b].push_back({ a, c });

			}

			pq.push({ { 0, s }, c });

			dijkstra();

			for (int i = 0; i <= c; i++)

				ans = min(ans, tocost[d][i]);

			cout << ans << endl;

		}

		return 0;

	}

// Fastest known solution for this problem: