#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <ctime>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
class Timer
{
  private:
    double time_limit;
    //unsigned long long int cycle_per_sec = 2500000000; // Topcoder
    unsigned long long int cycle_per_sec = 2777777777; // AtCoder
    unsigned long long int beginCycle;
    unsigned long long int getCycle()
    {
        unsigned int low, high;
        __asm__ volatile("rdtsc"
                         : "=a"(low), "=d"(high));
        return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
    }

  public:
    Timer(double time_limit) : time_limit(time_limit)
    {
        beginCycle = getCycle();
    }

    double elapsedTime()
    {

        return (double)(getCycle() - beginCycle) / cycle_per_sec;
    }
    bool isTLE()
    {
        return elapsedTime() >= time_limit;
    }
};

Timer gtimer(2.85);

struct NODE
{
    int to, cost, ticket;
    NODE(int to, int cost, int ticket) : to(to), cost(cost), ticket(ticket) {}
};
bool operator<(const NODE &a, const NODE &b)
{
    return a.cost > b.cost;
}
int main()
{
    int c, n, m, s, d;
    while (cin >> c >> n >> m >> s >> d && c)
    {
        vector<NODE> g[110];

        for (int i = 0; i < m; i++)
        {
            int a, b, f;
            cin >> a >> b >> f;
            --a, --b;
            g[a].push_back(NODE(b, f, 0));
            g[b].push_back(NODE(a, f, 0));
            g[a].push_back(NODE(b, f / 2, 1));
            g[b].push_back(NODE(a, f / 2, 1));
        }
        --s, --d;
        priority_queue<NODE> Q;
        Q.push(NODE(s, 0, c));
        int done[110][11] = {};
        while (Q.size())
        {
            auto q = Q.top();
            Q.pop();
            if (q.ticket < 0)
                continue;
            if (done[q.to][q.ticket]++)
                continue;
            if (q.to == d)
            {
                cout << q.cost << endl;
                break;
            }
            for (auto e : g[q.to])
            {
                Q.push(NODE(e.to, q.cost + e.cost, q.ticket - e.ticket));
            }
        }
    }

    std::cout.flush();
    return 0;
}