#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
// Policy based data structure
typedef tree<int, null_type,
less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update>
indexed_set;
#define ll long long int
#define pii pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define vi vector<ll>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define yes cout<<"YES"<<endl; return;
#define no cout<<"NO"<<endl; return;
#define flus fflush(stdin); fflush(stdout);
#define F first
#define S second
#define np next_permutation
#define inf 1e18
#define mod 1000000007
#define N 1005
#define pi (double)2*acos(0.0)
#define minpq priority_queue <ll, vector<ll>, greater<ll>>
#define maxpq priority_queue<ll>
/*******************************************************************/
struct state{
ll dist,node,used;
state(ll dist1,ll node1,ll used1){
dist=dist1;
node=node1;
used=used1;
}
bool operator<(const state&s) const{
if(this->dist==s.dist){
if(this->node==s.node){
return this->used < s.used;
} else{
return this->node < s.node;
}
} else{
return this->dist < s.dist;
}
}
};
ll n,m,a,b,k;
vii adj[N];
ll dist[N][N];
void solve(){
cin>>n>>m>>a>>b>>k;
rep(i,0,m){
ll u,v,w;
cin>>u>>v>>w;
adj[u].eb(v,w);
adj[v].eb(u,w);
}
rep(i,0,n+1){
rep(j,0,k+1){
dist[i][j]=inf;
}
}
rep(i,0,k+1){
dist[a][i]=0;
}
map<pii,pii> pa;
set<state> s;
s.insert(state(0,a,0));
while(!s.empty()){
state curr=*s.begin();
// curr.print();
s.erase(s.begin());
for(auto ch:adj[curr.node]){
if(dist[ch.F][curr.used]>dist[curr.node][curr.used] + ch.S){
state temp(dist[ch.F][curr.used],ch.F,curr.used);
auto it=s.find(temp);
if(it!=s.end())
s.erase(it);
dist[ch.F][curr.used]=dist[curr.node][curr.used] + ch.S;
pa[{ch.F,curr.used}]={curr.node,curr.used};
temp.dist=dist[ch.F][curr.used];
s.insert(temp);
}
if(curr.used+1<=k and dist[ch.F][curr.used+1]>dist[curr.node][curr.used]){
state temp(dist[ch.F][curr.used+1],ch.F,curr.used+1);
auto it=s.find(temp);
if(it!=s.end())
s.erase(it);
dist[ch.F][curr.used+1]=dist[curr.node][curr.used];
pa[{ch.F,curr.used+1}]={curr.node,curr.used};
temp.dist=dist[ch.F][curr.used+1];
s.insert(temp);
}
}
}
ll ans=inf;
rep(i,0,k+1){
ans=min(ans,dist[b][i]);
}
if(ans>=inf){
cout<<-1<<endl;
} else{
cout<<ans<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
// cin>>t;
t=1;
while(t--){
solve();
}
}