#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>

#define INF 1010000000
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,n) for(int i=1;i<=n;i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);

using namespace std;

class S{
	public:
	int p;
	int v;
	int n;
	
	S(int p,int v,int n):p(p),v(v),n(n){}
	
	bool operator<(const S&a)const{
		return v>a.v;
		return v==a.v ? v>a.v : n <a.n;
	}
};

int main(){
	while(1){
		int c,n,m,s,g;
		scanf("%d%d%d%d%d",&c,&n,&m,&s,&g);
		if(c==0&&n==0)break;
		
		int root[101][101];
		rep(i,101)rep(j,101)root[i][j]=INF;
		
		rep(i,m){
			int a,b,d;
			sinttt(a,b,d);
			root[a][b]=d;
			root[b][a]=d;
		}
		
		priority_queue<S> qui;
		qui.push(S(s,0,0));
		int ans=0;
		
		int visit[101][11];
		rep(i,101)rep(j,11)visit[i][j]=0;
		
		while(1){
			if(qui.empty()==1){
				ans=-1;
				break;
			}
			
			S u=qui.top();qui.pop();
			
			if(u.p==g){
				ans=u.v;
				break;
			}
			
			printf("%d %d %d\n",u.p,u.v,u.n);
			visit[u.p][u.n]=1;
			
			reps(i,n){
				if(root[u.p][i]!=INF){
					if(visit[i][u.n]==0){
						qui.push(S(i,u.v+root[u.p][i],u.n));
					}
					if(visit[i][u.n+1]==0 && visit[u.p][u.n+1]==0 && u.n+1 <= c){
						qui.push(S(i,u.v+root[u.p][i]/2,u.n+1));
					}
				}
			}
		}
		printf("%d\n",ans);
	}
}