#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<eps)
struct edge
{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};
int c,n,m,s,d;
int id(int index,int rem)
{
	return ((c+1)*index+rem);
}
vector<edge> g[2000];
int dist[2000];
void dijkstra()
{
	for(int i=0;i<2000;i++)dist[i]=INF;
	dist[id(s,c)]=0;
	priority_queue<P,vector<P>,greater<P> > q;
	q.push(P(0,id(s,c)));
	while(!q.empty())
	{
		P a=q.top();
		q.pop();
		int v=a.sec;
		if(dist[v]<a.fi)continue;
		for(int i=0;i<g[v].size();i++)
		{
			edge e=g[v][i];
			if(dist[e.to]>dist[v]+e.cost)
			{
				dist[e.to]=dist[v]+e.cost;
				q.push(P(dist[e.to],e.to));
			}
		}
	}
	return;
}
int main()
{
	while(1)
	{
		scanf("%d %d %d %d %d",&c,&n,&m,&s,&d);
		if(c==0&&n==0&&m==0&&s==0&&d==0)break;
		s--;d--;
		for(int i=0;i<2000;i++)g[i].clear();
		for(int i=0;i<m;i++)
		{
			int A,B,C;
			scanf("%d %d %d",&A,&B,&C);
			A--;B--;
			for(int j=0;j<=c;j++)
			{
				g[id(A,j)].pb(edge(id(B,j),C));
				g[id(B,j)].pb(edge(id(A,j),C));
			}
			for(int j=1;j<=c;j++)
			{
				g[id(A,j)].pb(edge(id(B,j-1),C/2));
				g[id(B,j)].pb(edge(id(A,j-1),C/2));
			}
		}
		dijkstra();
		int ans=INF;
		for(int i=0;i<=c;i++)ans=min(ans,dist[id(d,i)]);
		printf("%d\n",ans);
	}
	return 0;
}