#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define MAX_V 100
#define INF 10000000
using namespace std;

struct edge{
  int to,cost;
};

typedef pair<int,int> P; //firstは最短経路,secondは頂点番号

vector<edge> G[MAX_V];
int vertexes,edges;
int d[MAX_V][MAX_V];

void dijkstra(int start,int tickets){
  priority_queue<P,vector<P>,greater<P> > que;
  for(int i=0;i<vertexes;i++) d[tickets][i] = INF;
  d[tickets][start] = 0;
  que.push(P(0,start));

  while(!que.empty()){
    P p = que.top();
    que.pop();
    int v = p.second; 
    if(d[tickets][v] < p.first) continue; //異なる2経路のコストで高い方は無視
    for(int i=0;i<G[v].size();i++){
      edge e = G[v][i];
      int minimum = (tickets==0 ? d[tickets][v] + e.cost: min(d[tickets][v] + e.cost, d[tickets-1][v] + e.cost/2));
      if(d[tickets][e.to] > minimum){
        d[tickets][e.to] = minimum;
        que.push( P(d[tickets][e.to],e.to) );
      }
    }
  }
}

int main(){
  int discounts,start,destination;
  while(cin >> discounts >> vertexes >> edges >> start >> destination){
    if(!discounts && !vertexes && !edges && !start && !destination) break;
    for(int i=0;i<edges;i++){
      int a,b,fee;
      cin >> a >> b >> fee;
      a--; b--;

      edge E;
      E.to = b;
      E.cost = fee;
      G[a].push_back(E);

      E.to = a;
      G[b].push_back(E);
    }
    start--; destination--;
    for(int i=0;i<=discounts;i++) dijkstra(start,i);
    cout << d[discounts][destination] << endl;
    for(int i=0;i<MAX_V;i++) G[i].clear();
  }
  return 0;
}