#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
#include<string>
#define reep(a,s,d) for(int a=d;a<s;a++)
#define rep(a,s) reep(a,s,0)
using namespace std;
struct edge{
    int to,cost,tick;
    edge(int to,int cost,int tick):to(to),cost(cost),tick(tick){}
    edge(){}
};
bool operator<(const edge &a,const edge &b){
    return a.cost>b.cost;
}
int main(){
    int c,n,m,s,d;
    while(cin>>c>>n>>m>>s>>d,c){
        vector<edge> G[128];
        rep(i,m){
            int a,b,c;
            cin>>a>>b>>c;
            G[--a].push_back(edge(--b,c,0));
            G[b].push_back(edge(a,c,0));
        }
        bool vis[16][128];
        memset(vis,false,sizeof(vis));
        priority_queue<edge> Q;
        Q.push(edge(s-1,0,0));
        int ret=-1;
        while(!Q.empty()){
            edge n=Q.top();Q.pop();
            if(vis[n.tick][n.to])continue;
            vis[n.tick][n.to]=true;
            if(n.to==d-1){
                ret=n.cost;
                break;
            }
            rep(i,G[n.to].size()){
                Q.push(edge(G[n.to][i].to,n.cost+G[n.to][i].cost,n.tick));
                if(n.tick<c){
                    Q.push(edge(G[n.to][i].to,n.cost+G[n.to][i].cost/2,n.tick+1));
                }
            }
        }
        cout<<ret<<endl;
    }
}