55pts 求条

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
#define MAXN 5000010
using namespace std;
const ll INF = 1e18;
struct Edge {
  ll v, w;
  friend bool operator<(const Edge &a, const Edge &b) {
    return a.w > b.w;
  }
  Edge(ll v_, ll w_) : v(v_), w(w_) {}
};
bool vis[MAXN];
ll dis[MAXN];
priority_queue<Edge> q;
vector<Edge> g[MAXN];
ll n, m, k, s, t, u, v, w, res;
void add(ll u, ll v, ll w) {
  g[u].emplace_back(v, w);
}
void dijkstra() {
  for (ll i = 1; i <= (k + 1) * n; i++)
    dis[i] = INF, vis[i] = false;
  dis[s] = 0;
  q.emplace(s, 0);
  while (!q.empty()) {
    ll u = q.top().v;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto &e : g[u]) {
      ll v = e.v, w = e.w;
      if (dis[v] > dis[u] + w)
        dis[v] = dis[u] + w, q.emplace(v, dis[v]);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k >> s >> t;
  for (ll i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    add(u, v, w), add(v, u, w);
    for (ll j = 1; j <= k; j++) {
      ll uj = u + j * n, vj = v + j * n;
      ll uj_1 = u + (j - 1) * n, vj_1 = v + (j - 1) * n;
      add(uj, vj, w), add(vj, uj, w);
      add(uj_1, vj, 0), add(vj_1, uj, 0);
    }
  } dijkstra(), res = INF;
  for (ll i = 0; i <= k; i++)
    res = min(res, dis[t + i * n]);
  cout << res << '\n';
  return 0;
}