#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

#define INF 1111111111
#define F first
#define S second

struct edge {
  int to, cost;
  edge(int _to, int _cost) {to = _to; cost=_cost;}
};
typedef pair<int, pair<int, int> > P;

vector<edge> G[512];
int d[16][512];
int c, n, m, s, g;

void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d[0], d[0] + 16 * 512, INF);
  d[c][s] = 0;
  que.push(P(0, pair<int, int>(s, c)));
  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.S.F; int w = p.S.S;
    if(d[w][v] < p.F) continue;
    for(int i = 0;i < G[v].size(); i++){
      edge e = G[v][i];
      if(d[w][e.to] > d[w][v] + e.cost){
        d[w][e.to] = d[w][v] + e.cost;
        que.push(P(d[w][e.to], pair<int, int>(e.to, w)));
      }
      if(w > 0 && d[w - 1][e.to] > d[w][v] + e.cost / 2){
	d[w - 1][e.to] = d[w][v] + e.cost / 2;
	que.push(P(d[w - 1][e.to], pair<int, int>(e.to, w - 1)));
      }
    }
  }
}

int main(void){
  int a, b, f;
  for( ; ; ){
    for(int i = 0;i < 512; i++) G[i].clear();
    scanf("%d %d %d %d %d", &c, &n, &m, &s, &g);
    if(!(c + n + m + s + g)) break;
    for(int i = 0;i < m; i++){
      scanf("%d %d %d", &a, &b, &f);
      G[a].push_back(edge(b,f));
      G[b].push_back(edge(a,f));
    }
    
    dijkstra(s);
    int ans = INF;
    for(int i = 0;i <= c; i++) ans = min(ans, d[i][g]);
    printf("%d\n", ans);
  }
}
