#include<stdio.h>
#include<string.h>
#include<queue>
#include<functional>
#include<algorithm>
using namespace std;
struct S{int i,c,r;};
struct C:binary_function<S,S,int>{int operator()(S l,S r){return l.c>r.c;}};
int main()
{
	int c,n,m,s,d,i,a,b,f,_=0x3f3f3f3f;
	int g[100][100];
	int x[100][11];
	while(scanf("%d%d%d%d%d",&c,&n,&m,&s,&d),c)
	{
		memset(g,63,sizeof(g));
		memset(x,63,sizeof(x));
		for(i=0;i<m;++i)
		{
			scanf("%d%d%d",&a,&b,&f);
			g[a-1][b-1]=g[b-1][a-1]=f;
		}
		S p,t;
		p.c=0;
		p.r=c;
		p.i=s-1;
		priority_queue<S,vector<S>,C>q;
		q.push(p);
		while(!q.empty())
		{
			p=q.top();q.pop();
			if(x[p.i][p.r]<=p.c)continue;
			x[p.i][p.r]=p.c;
			for(i=0;i<n;++i)
			{
				if(g[p.i][i]==_)continue;
				if(p.r)
				{
					t=p;
					t.r--;
					t.c+=g[t.i][i]/2;
					t.i=i;
					q.push(t);
				}
				t=p;
				t.c+=g[t.i][i];
				t.i=i;
				q.push(t);
			}
		}
		printf("%d\n",*min_element(x[d-1],x[d]));
	}
	return 0;
}