// AOJ 0212 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212)
#include<cstdio>
#include<algorithm>
#include<limits>
#include<queue>
#include<vector>
#define rep(i,a) for(int i=0;i<(a);++i)

typedef std::pair<int, int> P;

const int MAX_N = 100, MAX_C = 10, INF = std::numeric_limits<int>::max()>>2;

struct St
{
	int v, dist, tick;

	St( int v, int dist, int tick )
	:	v(v), dist(dist), tick(tick)
	{}

	bool operator< ( const St &s ) const
	{ return dist > s.dist; }
};

int c, n, m, s, d;
std::vector<P> G[MAX_N];
int dp[MAX_N][MAX_C];

int main()
{
	while( scanf( "%d%d%d%d%d", &c, &n, &m, &s, &d ), c|n|m|s|d )
	{
		rep( i, n )
			G[i].clear();

		--s; --d;

		rep( i, m )
		{
			int a, b, f;
			scanf( "%d%d%d", &a, &b, &f );
			--a; --b;
			G[a].push_back( P( b, f ) );
			G[b].push_back( P( a, f ) );
		}

		std::priority_queue<St> pque;
		pque.push( St( s, 0, c ) );
		
		rep( i, n ) rep( j, c+1 )
			dp[i][j] = INF;
		dp[s][c] = 0;
		
		while( !pque.empty() )
		{
			St st = pque.top(); pque.pop();
			int v = st.v, dist = st.dist, t = st.tick;

			if( dp[v][t] < dist )
				continue;

			rep( i, G[v].size() )
			{
				P &e = G[v][i];

				if( dp[e.first][t] > dp[v][t]+e.second )
				{
					dp[e.first][t] = dp[v][t]+e.second;
					pque.push( St( e.first, dp[v][t]+e.second, t ) );
				}

				if( t && dp[e.first][t-1] > dp[v][t]+e.second/2 )
				{
					dp[e.first][t-1] = dp[v][t]+e.second/2;
					pque.push( St( e.first, dp[v][t]+e.second/2, t-1 ) );
				}
			}
		}

		printf( "%d\n", *std::min_element( dp[d], dp[d]+c+1 ) );
	}

	return 0;
}