#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int INF = 1 << 30;
const int MOD = 1e9 + 7;
const int MAX_N = 110;
struct edge
{
    int to, cost, card;
    bool operator<(const edge &a) const { return cost > a.cost; }
};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d, c | n | m)
    {
        s--, d--;
        vector<edge> G[MAX_N];
        for (int i = 0; i < m; i++)
        {
            int a, b, f;
            cin >> a >> b >> f;
            a--, b--;
            G[a].push_back({b, f, 0});
            G[b].push_back({a, f, 0});
            G[a].push_back({b, f / 2, 1});
            G[b].push_back({a, f / 2, 1});
        }
        priority_queue<edge> que;
        vector<vector<int>> dist(n, vector<int>(15, INF));
        dist[s][c] = 0;
        que.push({s, 0, c});
        while(que.size())
        {
            edge p = que.top(); que.pop();
            for(int u = 0; u < G[p.to].size(); u++)
            {
                edge e = G[p.to][u];
                int num = p. card - e.card;
                if(num < 0) continue;
                if(e.cost + dist[p.to][p.card] < dist[e.to][num])
                {
                    dist[e.to][num] = dist[p.to][p.card] + e.cost;
                    que.push({e.to, dist[e.to][num], num});
                }
            }
        }
        int ans = INF;
        for(int i = 0; i < 15; i++) ans = min(ans, dist[d][i]);
        cout << ans << endl;
    }
    return 0;
}
