#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <cstdlib>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

inline int ReadInt()
{
    int x = 0, neg = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            neg = -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = x * 10 + c ^ 48;
        c = getchar();
    }
    return x;
}

const int N = 1e4 + 10, M = 5e4 + 10, K = 10;
int n, m, k, head[(K + 1) * N], dis[(K + 1) * N], tot;
struct E
{
    int to, next, weight;
} edge[4 * M * K + 2 * M];

void add(int from, int to, int weight)
{
    edge[++tot].next = head[from];
    head[from] = tot;
    edge[tot].to = to;
    edge[tot].weight = weight;
}

struct node
{
    int id, value;
    node(int x, int y)
    {
        id = x, value = y;
    }

    bool operator < (const node &n) const
    {
        return value > n.value;
    }
};
void dijkstra(int start)
{
    priority_queue<node> q;
    bool vis[(K + 1) * N];
    
    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));

    dis[start] = 0;
    q.push(node(start, dis[start]));

    while (!q.empty())
    {
        int u = q.top().id;
        q.pop();

        if (vis[u])
            continue;
        vis[u] = true;

        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].to, w = edge[i].weight;

            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push(node(v, dis[v]));
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    n = ReadInt(), m = ReadInt(), k = ReadInt();
    int s = ReadInt(), t = ReadInt();
    for (int i = 1; i <= m; i++)
    {
        int u = ReadInt(), v = ReadInt(), w = ReadInt();
        add(u, v, w);
        add(v, u, w);
        for (int j = 1; j <= k; j++)
        {
            add(n * (j - 1) + u, n * j + v, 0);
            add(n * (j - 1) + v, n * j + u, 0);
            add(n * j + u, n * j + v, w);
            add(n * j + v, n * j + u, w);
        }
    }

    for (int i = 1; i <= k; i++)
        add(n * (i - 1) + t, n * i + t, 0);

    dijkstra(s);

    cout << dis[n * k + t];

    return 0;
}