#include<iostream>
#include<queue>
#include<string.h>
using namespace std;

const int INF = 1<<30;

struct Node{
  int use,to,weight;
  Node() {;}
  Node(int use,int to,int weight) : use(use), to(to), weight(weight) {;}
};
bool operator<(const Node &e,const Node &f) {
  return e.weight > f.weight;
}

int dist[100][100];
bool visit[100];
int dist2[100][100];

int main() {
  int c,n,m,s,d,a,b,f;
    while(cin>>c>>n>>m>>s>>d, c|n|m|s|d) {
      s--,d--;

      for(int i=0; i<100; ++i) {
	for(int j=0; j<100; ++j) {
	  dist[i][j] = INF;
	}
	visit[i] = false;
      }

      for(int i=0; i<100; ++i)
	for(int j=0; j<100; ++j)
	  dist2[i][j] = INF;

      for(int i=0; i<m; ++i) {
	cin>>a>>b>>f;
	a--,b--;
	dist[a][b] = f;
	dist[b][a] = f;
      }

      priority_queue<Node> Q;
      Q.push(Node(0,s,0));
      visit[s] = true;
      while(!Q.empty()) {
	Node now = Q.top(); Q.pop();
	if(now.to == d) {
	  cout<<now.weight<<endl;
	  break;
	}

	visit[now.to] = true;
	for(int i=0; i<n; ++i) {
	  if(!visit[i] && dist[now.to][i] != INF) {
	    if(dist2[now.use+1][i]
	       > now.weight + dist[now.to][i]/2 && now.use < c) {
	      dist2[now.use+1][i] = now.weight + dist[now.to][i]/2;
	      Q.push(Node(now.use+1, i, dist2[now.use+1][i]));
	    }
	    if(dist2[now.use][i]
	       > now.weight + dist[now.to][i]) {
	      dist2[now.use][i] = now.weight + dist[now.to][i];
	      Q.push(Node(now.use, i, dist2[now.use][i]));
	    }
	  }
	}
      }
    }
}