#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

#define INF 100000000

using namespace std;

typedef pair<int,int> paii;

int c, n, m, s, d; 
int fare[1000][1000];
int vtx[1000][1000];
	
int solve()
{
	queue<paii> qu;
	CLR(vtx);
	
	FOR(i, 1, n+1)
	{
		FOR(j, 0, c+1)
		{
			if( i != s )
				vtx[i][j] = INF;
		}
	}
	
	qu.push(paii(s, c));
	
	while( !qu.empty() )
	{
		int nowv = qu.front().first;
		int nowt = qu.front().second;
		qu.pop();
		
		FOR(j, 1, n+1)
		{
			if(( j != nowv) && (fare[nowv][j] != 0))
			{
				if( vtx[j][nowt] > vtx[nowv][nowt] + fare[nowv][j] )
				{
					vtx[j][nowt] = vtx[nowv][nowt] + fare[nowv][j];
					qu.push(paii(j,nowt));
				}
				
				if( (nowt > 0) && (vtx[j][nowt-1] > vtx[nowv][nowt] + fare[nowv][j]/2) )
				{
					vtx[j][nowt-1] = vtx[nowv][nowt] + fare[nowv][j]/2;
					qu.push(paii(j,nowt-1));
				}
			}
		}
	}
	
	int res = INF;
	
	FOR(i, 0, c)
	{
		res = min(res, vtx[d][i]);
	}
	
	return res;
}

int main()
{
	while(cin >> c >> n >> m >> s >> d, (c||n||m||s||d))
	{
		CLR(fare);
		
		FOR(i, 0, m)
		{
			int a, b, f;
			cin >> a >> b >> f;
			
			fare[a][b] = f;
			fare[b][a] = f;
		}
		
		cout << solve() << endl;
	}
	
	return 0;
}