#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 1e+9
typedef pair<int,int> P;
struct edge{
    int to,cost;
};
int c,n,m,s,end;
vector<edge> G[101];
int d[11][101];

void dijkstra(int s,int a){
    priority_queue<P, vector<P>, greater<P> >Q;
    for(int i=0;i<n;i++)d[a][i] = INF;
    d[a][s] = 0;
    Q.push(P(0,s));
    
    while(!Q.empty()){
        P p=Q.top();
        Q.pop();
        int v = p.second;
        
        if(d[a][v] < p.first)continue;
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            int dm;
            if(a==0)dm=d[a][v]+e.cost;
            else dm=min(d[a][v]+e.cost,d[a-1][v]+e.cost/2);
            if(d[a][e.to] > dm){
                d[a][e.to] = dm;
                Q.push(P(d[a][e.to],e.to));
            }
        }
    }
}

int main() {
    while(1){
     cin>>c>>n>>m>>s>>end;
     s--;
     end--;
     if(!c)break;
     
     for(int i=0;i<m;i++){
         int a,b,f;
         cin>>a>>b>>f;
         a--;
         b--;
         G[a].push_back((edge){b,f});
         G[b].push_back((edge){a,f});
     }
     int ans = INF;
     for(int i=0;i<=c;i++){
         dijkstra(s,i);
	 }
        
     cout<<d[c][end]<<endl;
     
     for(int i=0;i<100;i++)G[i].clear();
	}
	return 0;
}