#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
typedef int Weight;
Weight INF = 1000000000;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
}

// Dijkstra (Verified: AOJ2005)
void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int main() {
  while(true) {
    int c,n,m,s,d;
    cin>>c>>n>>m>>s>>d;
    if(!c) break;
    --s;--d;
    Graph g(n*(c+1));
    REP(i,m) {
      int a,b,f;
      cin>>a>>b>>f;
      --a;--b;
      REP(j,c+1) {
        add_edge(g, j*n+a, j*n+b, f);
        add_edge(g, j*n+b, j*n+a, f);
      }
      REP(j,c) {
        add_edge(g, j*n+a, (j+1)*n+b, f/2);
        add_edge(g, j*n+b, (j+1)*n+a, f/2);
      }
    }
    REP(i,n) {
      REP(j,c) {
        add_edge(g, j*n+i, (j+1)*n+i, 0);
      }
    }
    Array ary;
    dijkstra(g, ary, s);
    cout<<ary[c*n+d]<<endl;
  }
  return 0;
}