#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <functional>

using namespace std;

//#define LOG(...) printf(__VA_ARGS__)
#define LOG(...)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define INF INT_MAX

struct P
{
    int n,cost,ticket;
    bool operator >(const P &p) const{
        return cost>p.cost;
    }
};

struct E{
    int to,cost;
};


int main() {
    int c,n,m,s,d;
    while(cin >> c >> n >> m >> s >> d,c|n|m|s|d){
        vector<vector<E>> edge=vector<vector<E>>(n+1);
        REP(i, m){
            int from,to,cost;
            cin >> from >> to >> cost;
            edge[from].push_back({to,cost});
            edge[to].push_back({from,cost});
        }

        int cost=INF;
        priority_queue<P, vector<P>, greater<P>> que;
        vvi town(n+1, vi(c+1, INF));

        que.push({s,0,c});
        while(!que.empty()){
            P p=que.top();que.pop();
            LOG("n:%d cost:%d tic:%d\n",p.n,p.cost,p.ticket);

            if(p.n==d){
                cost=p.cost;
                break;
            }

            REP(i, edge[p.n].size()){
                E e=edge[p.n][i];
                int ncost=p.cost+e.cost;
                if(town[e.to][p.ticket]>ncost){
                    LOG("afds n:%d cost:%d tic:%d\n",e.to,ncost,p.ticket);
                    town[e.to][p.ticket]=ncost;
                    que.push({e.to,ncost,p.ticket});
                }
                if(p.ticket>0){
                    ncost=p.cost+e.cost/2;
                    if(town[e.to][p.ticket-1]>ncost){
                        LOG("afds n:%d cost:%d tic:%d\n",e.to,ncost,p.ticket-1);
                        town[e.to][p.ticket-1]=ncost;
                        que.push({e.to,ncost,p.ticket-1});
                    }
                }
            }
        }

        cout << cost << endl;
    }
}