#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[110][110];
bool visited[110][110];
int cost[110][110];

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<110; ++i) {
	for(int j=0; j<110; ++j) {
	  dist[i][j] = INF;
	  cost[i][j] = INF;
	  visited[i][j] = false;
	}
      }

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

      priority_queue<Node> Q;
      Q.push(Node(0,s,0));
      while(!Q.empty()) {
	Node now = Q.top(); Q.pop();
	if(visited[now.use][now.to]) continue;
	visited[now.use][now.to] = true;

	if(now.to == d) {
	  cout<<now.weight<<endl;
	  break;
	}

	int from = now.to;
	for(int to=0; to<n; ++to) {
	  if(cost[from][to] == INF) continue;
	  int nuse = now.use;
	  if(nuse < c && !visited[nuse+1][to]) {
	    int newcost = now.weight + cost[from][to]/2;
	    if(newcost < dist[nuse+1][to]) {
	      dist[nuse+1][to] = newcost;
	      Q.push(Node(nuse+1, to, newcost));
	    }
	  }
	  if(!visited[nuse][to]) {
	    int newcost = now.weight + cost[from][to];
	    if(newcost < dist[nuse][to]) {
	      dist[nuse][to] = newcost;
	      Q.push(Node(nuse, to, newcost));
	    }
	  }
	}
      }
    }
}