#include <bits/stdc++.h>
#define F first
#define S second
#define INF 1<<28
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
typedef struct{
  int to;
  int cost;
}Edge;
int d[11111];
priority_queue<PP,vector<PP>,greater<PP> > pq;
int main(){
  int c,n,m,st,go;
  cin >> c >> n >> m >> st >> go;
  int a,b,f;
  fill(d,d+m,INF);
  vector<Edge> G[1111];
  for(int i=0;i<m;i++){
    cin >> a >> b >> f;
    G[a].push_back((Edge){b,f});
    G[b].push_back((Edge){a,f});
  }
  
  pq.push(PP(0,P(st,c)));
  while(!pq.empty()){
    PP p=pq.top();
    pq.pop();
    if(p.S.S){//割引券がまだあったら
      for(int i=0;i<G[p.S.S].size();i++){
	Edge e=G[p.S.S][i];
	if(d[e.to] > d[p.S.S] + (e.cost/2)){
	  d[e.to] = d[p.S.S] + (e.cost/2);
	  pq.push(PP(d[e.to],P(e.to,p.S.S-1)));
	}
      }
    }else{
      for(int i=0;i<G[p.S.S].size();i++){
	Edge e=G[p.S.S][i];
	if(d[e.to] > d[p.S.S] + e.cost){
	  d[e.to] = d[p.S.S] + e.cost;
	  pq.push(PP(d[e.to],P(e.to,p.S.S)));
	}
      }
    }
  }
  cout << d[go-1] << endl;
}