P4568

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = INT_MAX;
typedef pair<int, int> PII;

int n, m, k, s, t;
int d[N][11];
struct node
{
    int u, v;
};
vector<node> g[N];
bool vis[N];
void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > q;
    for(int i = 0;i <= k;i ++ ) d[s][i] = 0;
    for(int i = 0;i <= k;i ++ )
    {
        q.push(make_pair(0, s));
        while(q.size())
        {
            int x = q.top().second; q.pop();
            if(vis[x]) continue;
            vis[x] = true;
            for(int j = 0;j < g[x].size();j ++ )
            {
                int y = g[x][j].u;
                int f = 0;
                if(i && d[y][i] > d[x][i - 1])
                {
                    d[y][i] = d[x][i - 1];
                    q.push(make_pair(d[y][i], y)), f = 1;
                }
                if(d[y][i] > d[x][i] + g[x][j].v)
                {
                    d[y][i] = d[x][i] + g[x][j].v;
                    if(f == 0) q.push(make_pair(d[y][i], y));
                }
            }
            
        }
        memset(vis, false, sizeof(vis));
    }
}

int main(){
    cin >> n >> m >> k;
    cin >> s >> t;
    for(int i = 1;i <= m;i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int i = 0;i < n;i ++ )
    {
        for(int j = 0;j <= k;j ++ )
        {
            d[i][j] = inf;
        }
    }
    dijkstra();
    int ans = inf;
    for(int i = 0;i <= k;i ++ ) ans = min(ans, d[t][i]);
    cout << ans << endl;
    return 0;
}