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

#define MAX 110
#define INF (1<<29)
typedef pair<int, int> P;
typedef pair<int, P> P2;

struct edge{
  int to, cost;
};

vector<edge> G[MAX];
int V[MAX][11];
int ticket, n, m, s, d;

int dijkstra(){
  for(int i = 0 ; i < n ; i++)
    for(int j = 0 ; j < 11 ; j++) V[i][j] = INF;
  
  priority_queue<P2, vector<P2>, greater<P2> > que;
  
  que.push(P2(0, P(s, 0)));
  V[s][0] = 0;
  
  while(!que.empty()){
    P2 q = que.top(); que.pop();
    int v = q.second.first;
    int cnt = q.second.second;
    if(V[v][cnt] < q.first) continue;
    
    for(int i = 0 ; i < G[v].size() ; i++){
      edge e = G[v][i];
      if(V[e.to][cnt] > V[v][cnt] + e.cost){
	V[e.to][cnt] = V[v][cnt] + e.cost;
	que.push(P2(V[e.to][cnt], P(e.to, cnt)));
      }
      if(cnt >= ticket) continue;
      
      if(V[e.to][cnt+1] > V[v][cnt] + e.cost/2){
	V[e.to][cnt+1] = V[v][cnt] + e.cost/2;
	que.push(P2(V[e.to][cnt+1], P(e.to, cnt+1)));
      }
    }
  }
  int ret = INF;
  for(int i = 0 ; i <= ticket ; i++){
    ret = min(ret, V[d][i]);
  }
  return ret;
}

int main(){
  while(cin >> ticket >> n >> m >> s >> d){
    if(!ticket && !n && !m && !s && !d) break;
    s--, d--;    
    for(int i = 0 ; i < n ; i++) G[i].clear();
    int from, to, cost;
    for(int i = 0 ; i < m ; i++){
      cin >> from >> to >> cost;
      from--, to--;
      edge e;
      //無向グラフ
      e.to = to, e.cost = cost;
      G[from].push_back(e);
      e.to = from; 
      G[to].push_back(e);
    }
    cout << dijkstra() << endl;
  }
  return 0;
}