#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int f(int a[][101],int b[],int c[],int d,int n,int p,int e,int w){
  int h,i;
  int z[101];
  int sm,mn=-1;
  if(p==e){
    do{
      h=0;
      for(i=1;i<d;i++){
	if(c[i-1]<c[i]){
	  swap(c[i-1],c[i]);
	  h=1;
	}
      }
    }while(h);
    sm=0;
    for(i=0;i<d;i++)
      sm+=i<w?c[i]/2:c[i];
    return sm;
  }
  if(b[p])
    return -1;
  memcpy(z,b,sizeof(z));
  z[p]=1;
  for(i=1;i<n+1;i++){
    if(a[p][i]!=-1){
      int tmp;
      c[d]=a[p][i];
      if((tmp=f(a,z,c,d+1,n,i,e,w))!=-1){
	if(mn==-1||mn>tmp)
	  mn=tmp;
      }
    }
  }
  return mn;
}
int main(){
  int i;
  int a[101][101],b[101],c[99],w,m,n,s,e;
  memset(b,0,sizeof(b));
  while(cin>>w>>n>>m>>s>>e&&w+n+m+s+e!=0){
    memset(a,-1,sizeof(a));
    for(i=0;i<m;i++){
      int p,q,r;
      cin>>p>>q>>r;
      a[p][q]=r;
      a[q][p]=r;
    }
    cout<<f(a,b,c,0,n,s,e,w)<<endl;
  }
  return 0;
}
    