import std.stdio;
import std.container;
import std.algorithm;
import std.typecons;
import core.stdc.stdlib;

struct Node {
  int cost;
  int cnt;
  int v;
  int opCmp(const Node e) const {
    return (cost < e.cost) ? -1 : (cost > e.cost) ? +1 : 0;
  }
}

void main(){
  while(1){
    int c,n,m,s,d;
    scanf("%d %d %d %d %d", &c, &n, &m, &s, &d);
    if ((c | n | m | s | d) == 0)break;
    auto es = new Tuple!(int, int)[][n+1];
    foreach(i;0..m){
      int a, b, f;
      scanf("%d %d %d", &a, &b, &f);
      es[a] ~= tuple(f, b);
      es[b] ~= tuple(f, a);
    }
    auto visited = new bool[101][11];

    BinaryHeap!(Array!(Node), "a > b") q;
    q.insert(Node(0,c,s));
    exit(0);
    int ans = 2 << 28;
    while(!q.empty()){
      auto t = q.front;
      auto cost = t.cost;
      auto cnt = t.cnt;
      auto v = t.v;
      q.removeFront;
      stderr.writeln(v, " " , cnt, " " , cost);
      visited[v][cnt]=true;
      if(v == d){
        ans = min(cost, ans);
      }
      if(es[v]){
        foreach(e; es[v]){
          if(!visited[e[1]][cnt]){
          q.insert(Node(cost + e[0], cnt, e[1]));
          }
          if (cnt > 0 && !visited[e[1]][cnt-1])
            q.insert(Node(cost + e[0] / 2, cnt-1, e[1]));
        }
      }
    }
    writeln(ans);
  }
}