#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
struct state{
  int pos,money,cic;
  state(int pos=0,int money=0,int cic=0):
    pos(pos), money(money), cic(cic) {}
};
struct edge{
  int to,cost;
  edge(int to=0,int cost=0):
    to(to),cost(cost) {}
};
bool operator < (const state& s, const state& t){
  return s.money > t.money;
}

int main(void){
  int c,n,m,s,d;
  while(cin>>c>>n>>m>>s>>d){
    if(c==0) break;
    s--;d--;
    vector< vector<edge> > graph(n);
    REP(i,m){
      int a,b,f;
      cin>>a>>b>>f;
      a--;b--;
      graph[a].push_back(edge(b,f));
      graph[b].push_back(edge(a,f));
    }
    priority_queue<state> que;
    que.push(state(s));
    bool used[110][20]={};
    while(!que.empty()){
      state nowstate = que.top(); que.pop();
      int pos = nowstate.pos;
      int money = nowstate.money;
      int cicket = nowstate.cic;
      if(pos == d){
        cout<<money<<endl;
        break;
      }
      if(used[pos][cicket])continue;
      used[pos][cicket] = true;
      REP(i,graph[pos].size()){
        edge e = graph[pos][i];
        que.push(state(e.to,money+e.cost,cicket));
        if(cicket != c) que.push(state(e.to,money+e.cost/2,cicket+1));
      }
    }
  }
  return 0;
}