#include <cstdio> 
#include <algorithm> 
#include <queue> 
 
using namespace std; 
 
const int INF   = 100000000; 
const int C_MAX = 10; 
const int N_MAX = 100; 
 
// ¬Ìîñ 
// pair<cèÌø, ¬ÌÔ> 
typedef pair<int, int> T; 
 
// n_Ìîñ 
// pair<Å¬RXg, n_Ìîñ> 
typedef pair<int, T> P; 
 
// üÍ 
int c, n, m, s, d; 
 
// »Ì¬ÜÅÌÅ¬ÌRXg 
// cost[¬ÌÔ][cèÌø] = ïp 
int cost[N_MAX][C_MAX + 1]; 
 
// ùÉÅKlªèÏÝ©Ç¤© 
bool flag[N_MAX][C_MAX + 1]; 
 
// HüÌîñ 
// line[n_][I_] = ¿à 
int line[N_MAX][N_MAX]; 
 
// DP pL[ 
typedef priority_queue<P, vector<P>, greater<P> > Q; 
Q dp_q; 
 
// _CNXg@ 
int dijkstra(){ 
     
    while(!dp_q.empty()){ 
        P  p = dp_q.top(); dp_q.pop(); 
        T &t = p.second; 
         
        // ùÉÅKlªèÏÝ©²×é 
        if(flag[t.second][t.first]) continue; 
        flag[t.second][t.first] = true; 
         
        // ÅIn_ 
        if(t.second == d){ 
            return p.first; 
        } 
         
        for(int i = 0; i < n; ++i){ 
            // øðgíÈ¢ê 
            if(cost[i][t.first] > p.first + line[t.second][i]){ 
                cost[i][t.first] = p.first + line[t.second][i]; 
                dp_q.push(P(p.first + line[t.second][i], T(t.first, i))); 
            } 
             
            // øðg¤ê 
            if(t.first > 0 && cost[i][t.first - 1] > p.first + line[t.second][i] / 2){ 
                cost[i][t.first - 1] = p.first + line[t.second][i] / 2; 
                dp_q.push(P(p.first + line[t.second][i] / 2, T(t.first - 1, i))); 
            } 
        } 
    } 
     
    return INF; 
} 
 
void solve(){ 
     
    // ú» 
    for(int i = 0; i < N_MAX; ++i){ 
        for(int j = 0; j < C_MAX + 1; ++j){ 
            cost[i][j] = INF; 
            flag[i][j] = false; 
        } 
    } 
     
    // Jnn_ 
    dp_q = Q(); 
    dp_q.push(P(0, T(c, s))); 
     
    // _CNXg@ 
    printf("%d\n", dijkstra()); 
} 
 
int main(){ 
    int a, b, f; 
     
    while(scanf("%d %d %d %d %d", &c, &n, &m, &s, &d), c > 0){ 
        --s; 
        --d; 
         
        // ú» 
        for(int i = 0; i < N_MAX; ++i){ 
            for(int j = 0; j < N_MAX; ++j){ 
                line[i][j] = INF; 
            } 
        } 
         
        for(int i = 0; i < m; ++i){ 
            scanf("%d %d %d", &a, &b, &f); 
             
            --a; 
            --b; 
             
            line[a][b] = f; 
            line[b][a] = f; 
        } 
         
        solve(); 
    } 
     
    return 0; 
}