#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=1e9;
struct edge{int to,cost;};
int dp[100][11];
vector<edge> G[100];
int main(){
      int c,n,m,s,d;
      while(cin>>c>>n>>m>>s>>d&&(c||n||m||s||d)){
            s--;d--;
            REP(i,100)REP(j,11)dp[i][j]=INF;
            REP(i,100)G[i].clear();
            REP(i,m){
                  int x,y,z;
                  cin>>x>>y>>z;x--;y--;
                  G[x].PB((edge){y,z});
                  G[y].PB((edge){x,z});
            }
            dp[s][0]=0;
            queue<int> Q;
            Q.push(s);
            while(!Q.empty()){
                  int v=Q.front();Q.pop();
                  //cout<<v<<" "<<G[v].size()<<endl;
                  REP(i,G[v].size()){
                        bool f=false;
                        edge e=G[v][i];
                        int to=e.to;
                        REP(i,c+1){
                              //cout<<dp[v][i]+e.cost<<endl;;
                              if(dp[to][i]>dp[v][i]+e.cost){
                                    dp[to][i]=dp[v][i]+e.cost;
                                    f=true;
                              }
                        }
                        REP(i,c){
                              if(dp[to][i+1]>dp[v][i]+e.cost/2){
                                    dp[to][i+1]=dp[v][i]+e.cost/2;
                                    f=true;
                              }
                        }
                        if(f)Q.push(to);
                  }
            }
            int ans=INF;
            REP(i,c+1)ans=min(ans,dp[d][i]);
            cout<<ans<<endl;
      }
}