#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

int C;

// dijkstra O(ElogV)
// verify : https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A
template<typename T>
struct Dijkstra {
private:
    int V;
    struct edge { int to; T cost; };
    vector<vector<edge>> G;
public:
    const T inf = numeric_limits<T>::max();

    // s から i の最小コスト
    // 経路がない場合は inf
    vector<vector<T>> d;

    Dijkstra(int V) : V(V) {
        G.resize(V);
    }

    // 辺の追加
    // 有向の場合　directed = true
    void add_edge(int from, int to, T weight, bool directed = false) {
        G[from].push_back({to,weight});
        if (!directed) G[to].push_back({from,weight});
    }

    void build(int s) {
        d.assign(V, vector<T>(C+1,inf));
        typedef pair<pair<T,int>, int> P; //(cost,v)
        priority_queue<P, vector<P>, greater<P>> pq;
        d[s][0] = 0;
        pq.push(P({d[s][0],0}, s));
        while (!pq.empty()) {
            P p = pq.top(); pq.pop();
            int v = p.second;
            int c = p.first.first;
            int k = p.first.second;
            if (d[v][k] < c) continue;
            for (const edge &e : G[v])
            {
                // 最小値が更新されるとき push
                if (k < C && d[e.to][k+1] > d[v][k] + e.cost / 2) {
                    d[e.to][k + 1] = d[v][k] + e.cost / 2;
                    pq.push({{d[e.to][k + 1],k + 1}, e.to});
                }
                if (d[e.to][k] > d[v][k] + e.cost) {
                    d[e.to][k] = d[v][k] + e.cost;
                    pq.push({{d[e.to][k],k}, e.to});
                }
            }
        }
    }
};

int main() {
    while (true) {
        int n, m, s, d; cin >> C >> n >> m >> s >> d;
        if (!C) break;
        Dijkstra<ll> G(n);
        s--; d--;
        REP(i, m) {
            int a, b; ll c; scanf("%d %d %lld", &a, &b, &c);
            a--; b--;
            G.add_edge(a, b, c);
        }
        G.build(s);
        ll ans = LLINF;
        REP(i, C+1) {
            ans = min(ans, G.d[d][i]);
        }
        cout << ans << endl;
    }
    return 0;
}
