#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll MM = 1e4, NN = 12;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll N, M, K, S, T, Dis[MM][NN];

struct edge {
    ll to, w;

    edge(ll to_, ll w_) {
        to = to_;
        w = w_;
    }
};

vector<edge> V[MM];

struct node {
    ll id, dis, cnt;
    node(ll id_, ll dis_, ll cnt_) {
        id = id_;
        dis = dis_;
        cnt = cnt_;
    }
    bool operator<(const node &n) const {
        if (n.cnt != cnt) {
            return n.cnt < cnt;
        }
        return n.dis < dis;
    }
};

void dj(ll s)
{
    bool Done[MM][NN];
    for (ll i = 0; i < MM; i++)
    {
        for (ll j = 0; j < NN; j++)
        {
            Dis[i][j] = INF;
            Done[i][j] = false;
        }
    }

    priority_queue<node>Q;
    Dis[s][0] = 0;
    Q.push(node(s, Dis[s][0], 0));

    while (!Q.empty())
    {
        node cur = Q.top(); Q.pop();

        if (Done[cur.id][cur.cnt]) {
            continue;
        }

        Done[cur.id][cur.cnt] = true;

        for (ll i = 0; i < V[cur.id].size(); i++)
        {
            edge e = V[cur.id][i];
            
            if (cur.cnt < K && Dis[e.to][cur.cnt+1] > Dis[cur.id][cur.cnt]) {
                Dis[e.to][cur.cnt+1] = Dis[cur.id][cur.cnt];
                Q.push(node(e.to, Dis[e.to][cur.cnt+1], cur.cnt+1));
            }
            if (Dis[e.to][cur.cnt] > Dis[cur.id][cur.cnt] + e.w) {
                Dis[e.to][cur.cnt] = Dis[cur.id][cur.cnt] + e.w;
                Q.push(node(e.to, Dis[e.to][cur.cnt], cur.cnt));
            }
        }
    }
    
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N >> M >> K;
    cin >> S >> T;

    ll a, b, c;
    for (ll i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        V[a].push_back(edge(b, c));
        V[b].push_back(edge(a, c));
    }

    dj(S);

    ll Min = INF;
    for (ll i = 0; i <= K; i++)
    {
        Min = min(Min, Dis[T][i]);
    }
    cout << Min;
}

本来没写最后那个遍历寻找最小值的，最后一个测试点过不了，补上就ok了。为啥最后要遍历一边啊，不理解。