#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

//int dy[]={0, 0, 1, -1, 0};
//int dx[]={1, -1, 0, 0, 0};

struct edge{
  int to, cost;
};

int c, n, m, start, goal;
vector<edge> v[105];	       
vector<vector<int> > dp(11, vector<int>(105, 0));

int dijkstra(int s, int a){
  REP(i, 105) dp[a][i]=INF;
  dp[a][s]=0;

  priority_queue<P> q;
  q.push(P(0, s));
  while(!q.empty()){
    int u=q.top().second;
    if(dp[a][u]<q.top().first) continue;
    q.pop();

    REP(i, v[u].size()){
      int to=v[u][i].to;
      int cost=(a==0 ? v[u][i].cost+dp[a][u] : min(v[u][i].cost+dp[a][u], v[u][i].cost/2+dp[a-1][u]));
      if(dp[a][to]>cost){
	dp[a][to]=cost;
	q.push(P(-cost, to));
      }
    }
  }
}

int main(){
  while(1){
    scanf("%d%d%d%d%d", &c, &n, &m, &start, &goal);
    start--; goal--;
    if(c==0) return 0;
    
    REP(i, m){
      int from, to, f;
      scanf("%d%d%d", &from, &to, &f);
      from--; to--;
      v[to].push_back((edge){from, f});
      v[from].push_back((edge){to, f});
    }

    REP(i, c+1){
      dijkstra(start, i);
    }

    printf("%d\n", dp[c][goal]);

    REP(i, 105){
      v[i].erase(v[i].begin(), v[i].end());
    }
    REP(i, 11){
      dp[i].erase(dp[i].begin(), dp[i].end());
    }
  }
}