#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iterator>
#include <stack>
#include <list>
using namespace std;
#define INF 100000000
typedef long long int lli;
typedef pair<int,int> P;
const int MAX_V=101;
const int MAX_E=501;
int cost[MAX_V][MAX_V];
int d[MAX_V][11];
bool used[MAX_V][11];

int main(){
    int c,n,m,s,g;
    while(cin>>c>>n>>m>>s>>g){
        if(c==0&&n==0&&m==0&&s==0&&g==0) break;
        for(int i=1; i<=n; ++i){
            for(int j=0; j<=c; ++j){
            	d[i][j]=INF;
            	used[i][j]=false;
            }
            for(int j=1; j<=n; ++j){
                cost[i][j]=INF;
                cost[j][i]=INF;
            }
        }
        for(int i=0; i<m; ++i){
            int a,b,f;
            cin >> a >> b >> f;
            cost[a][b]=f;
            cost[b][a]=f;
        }
        d[s][0]=0;
        while(true){
            int v=-1;
            int cnt=-1;
            for(int u=1; u<=n; ++u){
            	for(int i=0; i<=c; ++i){
                	if(!used[u][i]&&(v==-1||d[u][i]<d[v][cnt])) {
                		v=u;
               			cnt=i;
                	}
                }
            }
            if(v==-1) break;
            used[v][cnt]=true;
            for(int u=1; u<=n; ++u){
            	if(cnt<c) d[u][cnt+1]=min(d[u][cnt+1],d[v][cnt]+cost[v][u]/2);
            	d[u][cnt]=min(d[u][cnt],d[v][cnt]+cost[v][u]);
            }
        }
        int ans=INF;
        for(int i=1; i<=n; ++i){
        	for(int j=1; j<=c; ++j){
        		ans=min(ans,d[g][j]);
        	}
        }
        cout << ans << "\n";
    }
    return 0;
}