#include <bits/stdc++.h>

using namespace std;

#define MAX 120
#define INF 1e9

struct Edge{
  int to,cost;
  Edge(int t,int c) : to(t),cost(c) {}
};

struct State{
  int cost,v,tic;
  State(int c,int v,int t) : cost(c),v(v),tic(t) {}
  bool operator < (const State &s)const{
    return cost > s.cost;
  }
};

int C,V,E,src,dst;
vector<Edge> G[MAX];

int dijkstra(){
  priority_queue<State> Q;
  Q.push(State(0,src,C));
  int dist[MAX][11];
  fill(dist[0],dist[0]+MAX*11,INF);
  dist[src][C] = 0;
  
  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    int v = s.v,t = s.tic;
    if(dist[v][t] < s.cost) continue;
    if(v == dst) return dist[v][t];
    
    for(int i = 0 ; i < (int)G[v].size() ; i++){
      Edge e = G[v][i];
      if(dist[v][t] + e.cost < dist[e.to][t]){
        dist[e.to][t] = dist[v][t] + e.cost;
        Q.push(State(dist[e.to][t],e.to,t));
      }
      if(t > 0){
        if(dist[v][t] + e.cost/2 < dist[e.to][t-1]){
          dist[e.to][t-1] = dist[v][t] + e.cost/2;
          Q.push(State(dist[e.to][t-1],e.to,t-1));
        }
      }
    }
  }
}

int main(){
  while(cin >> C >> V >> E >> src >> dst, C){
    src--; dst--;
    for(int i = 0 ; i < V ; i++){
      G[i].clear();
    }
    for(int i = 0 ; i < E ; i++){
      int a,b,c;
      cin >> a >> b >> c; a--; b--;
      G[a].push_back(Edge(b,c));
      G[b].push_back(Edge(a,c));
    }
    cout << dijkstra() << endl;
  }
  return 0;
}