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

const int INF=10000000;
typedef struct edge{
  int t,c;
  edge(){}
  edge(int t,int c):t(t),c(c){}
};
typedef pair<int ,pair<int,int> > P;


vector<edge> g[105];
int id[11][105];
int c,n,m,s,d;

int main(void){
  while(1){
    scanf("%d %d %d %d %d",&c,&n,&m,&s,&d);
    if(!c && !n && !m && !s && !d) break;
    for(int i=0;i<=n;i++)g[i].clear();

    for(int i=0;i<m;i++){
      int a,b,f;
      scanf("%d %d %d",&a,&b,&f);
      g[a].push_back(edge(b,f));
      g[b].push_back(edge(a,f));
    }


    priority_queue<P,vector<P>,greater<P> > que;
    for(int i=0;i<=c;i++) fill(id[i],id[i]+n+1,INF);
    for(int i=0;i<10;i++)id[i][s]=0;
    que.push(P(0,pair<int,int>(s,c)));
    while(!que.empty()){
      P p=que.top();
      que.pop();
      int v=p.second.first;
      int nc=p.second.second;
      if(id[c-nc][v]<p.first) continue;
      for(int i=0;i<g[v].size();i++){
	edge e = g[v][i];
	if(id[c-nc][e.t]>id[c-nc][v]+e.c){
	  id[c-nc][e.t]=id[c-nc][v]+e.c;
	  que.push(P(id[c-nc][e.t],pair<int,int>(e.t,nc)));
	}
	if(nc>0 && id[c-nc+1][e.t]>id[c-nc][v]+e.c/2){
	  id[c-nc+1][e.t]=id[c-nc][v]+e.c/2;
	  que.push(P(id[c-nc+1][e.t],pair<int,int>(e.t,nc-1)));
	}
      }
    }
    printf("%d\n",id[c][d]);
  }
}