#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9, M = 5e4 + 9, NN = 1.1e5 + 9, MM = 2.1e6 + 9;
int n, m, k, x, y, l = 0, an = INT_MAX, a[M], b[M], c[M], last[MM], ans[NN], vis[NN];
struct e1 {
  int f, t, p, w;
} g[MM];
struct e2 {
  int x;
  friend bool operator<(const e2 p, const e2 q) { return a[p.x] > a[q.x]; }
};
priority_queue<e2> q;
void add(int a, int b, int c) {
  g[++l] = e1{a, b, last[a], c};
  last[a] = l;
}
void dij(int b) {
  memset(ans, 0x3f, sizeof(ans));
  ans[b] = 0;
  q.push({b});
  while (!q.empty()) {
    e2 e = q.top();
    q.pop();
    if (vis[e.x]) continue;
    vis[e.x] = 1;
    for (int i = last[e.x]; i; i = g[i].p)
      if (!vis[g[i].t]) {
        ans[g[i].t] = min(ans[g[i].t], g[i].w + ans[e.x]);
        q.push({g[i].t});
      }
  }
}
int main() {
  scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d", a + i, b + i, c + i);
  for (int i = 0; i <= k; i++) {
    for (int j = 1; j <= m; j++) {
      add(a[j] + n * i, b[j] + n * i, c[j]);
      add(b[j] + n * i, a[j] + n * i, c[j]);
    }
    if (i) for (int j = 1; j <= m; j++) {
      add(a[j] + n * i - n, b[j] + n * i, 0);
      add(b[j] + n * i - n, a[j] + n * i, 0);
    }
  }
  dij(x);
  for (int i = y; i < n * (k + 1); i += n)
    an = min(an, ans[i]);
  printf("%d", an);
  return 0;
}

分层图+dijkstra算法