#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

class State
{
public:
	int p,c,u;
	State(int p, int c, int u)
	:p(p),c(c),u(u)
	{}
	
	bool operator<(const State& s) const
	{
		return c>s.c;
	}
};

typedef vector<pair<int, int> > Node;

int main()
{
	int c,n,m,s,d;
	while(scanf("%d%d%d%d%d", &c,&n,&m,&s,&d), (c||n||m||s||d))
	{
		Node node[101];
		while(m--)
		{
			int a,b,f;
			scanf("%d%d%d", &a,&b,&f);
			node[a].push_back(make_pair(b,f));
			node[b].push_back(make_pair(a,f));
		}
		
		priority_queue<State> q;
		q.push(State(s,0,0));
		bool v[10][101]={0};
		
		while(!q.empty())
		{
			State S=q.top(); q.pop();
			if(S.p==d)
			{
				printf("%d\n", S.c);
				break;
			}
			if(v[S.u][S.p]) continue;
			v[S.u][S.p]=1;
			
			for(int i=0; i<node[S.p].size(); i++)
			{
				pair<int, int> next=node[S.p][i];
				if(!v[S.u][next.first]) q.push(State(next.first, S.c+next.second, S.u));
				if(S.u!=c)
				{
					if(!v[S.u+1][next.first]) q.push(State(next.first, S.c+next.second/2, S.u+1));
				}
			}
		}
	}
}