#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)

const int INF = 1 << 24;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

typedef unsigned long long ull;

struct Edge{
    int to, cost;
};

int C, N, M, S, D;
int cost[110][110];
int d[110][20], used[110][20];

void dijkstra(){
    REP(i, 110){
        REP(j, 20){
            d[i][j] = INF;
            used[i][j] = 0;
        }
    }

    d[S][0] = 0;

    while(1){
        int u = -1, v = -1;
        REP(i, N){
            REP(j, C){
                if(!used[i][j] && (u == -1 || d[u][v] > d[i][j])){u = i; v = j;}
            }
        }

        if(u == -1){break;}
        used[u][v] = 1;

        REP(i, N){
            d[i][v+1] = std::min(d[i][v+1], d[u][v] + cost[u][i] / 2);
            d[i][v] = std::min(d[i][v], d[u][v] + cost[u][i]);
        }
    }
}

int main(){
    while(std::cin >> C >> N >> M >> S >> D, C){
        S--; D--;

        REP(i, 110){
            REP(j, 110){
                cost[i][j] = INF;
            }
        }

        REP(i, M){
            int from, to, co;
            std::cin >> from >> to >> co;
            from--; to--;
        
            cost[from][to] = co;
            cost[to][from] = co;
        }

        dijkstra();

        int res = INF;
        REP(i, C+1){
            res = std::min(res, d[D][i]);
        }

        std::cout << res << std::endl;
    }
}