#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10
#define MAX_N 100

typedef pair<int, int> pi;
typedef pair<int, pi> P;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct edge{ int to, cost;};

vector<vector<edge> >G(MAX_N);
int c, n, m;
int cost[MAX_N][MAX_N];
int d[MAX_N];

void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> >q;
  rep(i, n)d[i] = INF;
  d[s] = 0;
  q.push(P(0, pi(s, c)));

  while(!q.empty()){
    P p = q.top(); q.pop();
    //    printf("%d %d %d\n", p.F, p.S.F, p.S.S);
    int v = p.S.F;
    //    if(d[v] < p.first) continue;
    rep(i, G[v].size()){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
	d[e.to] = d[v] + e.cost;
	q.push(P(d[e.to], pi(e.to, p.S.S)));
      }
      if(p.S.S && d[e.to] > d[v] + e.cost/2){
	d[e.to] = d[v] + e.cost/2;
	//	d[v][1]--;
	q.push(P(d[e.to], pi(e.to, p.S.S-1)));
      }
    }
  }      
}

int main(){
  int s, g;
  while(scanf("%d%d%d%d%d", &c, &n, &m, &s, &g) && c+n+m+s+g){
    s--; g--;
    G.clear();
    G.resize(n);
    int a, b, f;
    rep(i, m){
      scanf("%d%d%d", &a, &b, &f);a--;b--;
      edge e; e.to = b; e.cost = f;
      G[a].PB(e);
      e.to = a;
      G[b].PB(e);
    }
    dijkstra(s);
    printf("%d\n", d[g]);
  }
  return 0;
}