#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) string((s).rbegin(), (s).rend())
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int INF = 10000;


class V{
public:
	int total;
	int ticket;
	int to;
};
bool operator>(const V &lh, const V &rh){
	return (lh.total > rh.total);
}


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

	cin >> c >> n >> m >> s >> d;
	n++;
	vector<vector<int> > fare(n, vector<int>(n, INF));
	rep(i, m){
		int a, b, f;
		cin >> a >> b >> f;
		fare[a][b] = fare[b][a] = f;
	}

	vector<vector<int> > done(c+1, vector<int>(n, 0));	// 確定済みか
	vector<vector<int> > best(c+1, vector<int>(n, INF));	// 最短

	V start;
	start.total = 0;
	start.ticket = 0;
	start.to = s;

	priority_queue<V, vector<V>, greater<V> > q;
	q.push(start);

	while(!q.empty()){
		V p = q.top();
		q.pop();

		if(done[p.ticket][p.to] != 0) continue;
		done[p.ticket][p.to] = 1;
		best[p.ticket][p.to] = p.total;

		rep(i, n){
			if(fare[p.to][i] == INF ) continue;
			V next;
			next.total = best[p.ticket][p.to] + fare[p.to][i];
			next.ticket = p.ticket;
			next.to = i;
			q.push(next);
			if(p.ticket < c){
				next.total = best[p.ticket][p.to] + fare[p.to][i]/2;
				next.ticket = p.ticket+1;
				next.to = i;
				q.push(next);
			}
		}
	}
	//rep(i, c+1){
	//	rep(j, n){
	//		printf("%5d", best[i][j]);
	//	}
	//	cout << endl;
	//}

	cout << best[c][d] << endl;

	return 0;
}