#include <iostream>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <functional>

#define MAX 1000000000
#define Debug(X) debug( __LINE__, X )

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

int c, n, m, s, d;
int route[101][101];
int cost[101];
std::vector<std::vector<int> > visited(101);
bool used[101];

template<class T>
void debug( int line, T dbg ){
	std::cout << line << ": " << dbg << std::endl;
}

int main(){
	while( std::cin >> c >> n >> m >> s >> d, c * n * m * s * d ){
		for( int i = 0; i < 101 * 101; ++i )
			route[i / 101][i % 101] = MAX;
		for( int i = 0; i < 101; ++i )
			cost[i] = MAX;

		memset( used, 0, sizeof( used ) );
		visited.clear();

		unsigned int tmp[3];
		while( m-- ){
			int cnt = 3;
			while( cnt-- ) std::cin >> tmp[2 - cnt];

			route[tmp[0]][tmp[1]] = tmp[2];
			route[tmp[1]][tmp[0]] = tmp[2];
		}

		cost[s] = 0;
		
		while( true ){
			unsigned pos = 0;
			for( int i = 1; i <= n; ++i ){
				if( !used[i] && (pos == 0 || cost[pos] > cost[i]) ) pos = i;
			}
			
			used[pos] = 1;
			if( pos == 0 ) break;
					
			for( int i = 1; i <= n; ++i ){
				if( i != pos ){
					std::vector<int> tmpv;
					tmpv = visited[pos];
					tmpv.push_back( route[pos][i] );
					std::sort( tmpv.begin(), tmpv.end(), std::greater<int>() );
					
					int cnt = 0;
					for( int l = 0; l < tmpv.size(); ++l ){
						if( l < c ) cnt += tmpv[l] / 2;
						else cnt += tmpv[l];
					}
					if( cnt < cost[i] ){
						cost[i] = cnt;
						visited[i] = tmpv;
					}
					
				}
			}
		}

		std::cout << cost[d] << std::endl;
	}

	return 0;
}