（分层图最短路）给定一个含 n 个点、m 条边的无向连通图，边权均为非负整数。你有一个特殊道具：在整个过程中，最多可以把 K 条经过的边变为“免费边”，即第一次经过这些边时费用为 0（之后再经过仍按原费用计算）。点和边均允许重复经过。求从结点 1 到结点 n 的最小总费用。

以下代码求解了上述问题。它把“已经使用了多少次免费机会”作为状态的一维，在分层图上用堆优化的 Dijkstra 求最短路。试补全程序。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100005;
const long long INF = (long long)4e18;

struct Edge { int to, w; };
struct Node {
    long long d; int u, k;
    bool operator<(const Node &o) const { return d > o.d; }
};

int n, m, K;
vector<Edge> g[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<vector<long long>> dist(n + 1, vector<long long>(K + 1, INF));
    priority_queue<Node> pq;
    dist[1][0] = 0;
    pq.push({0, 1, ___①___});
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int u = cur.u, k = cur.k;
        if (___②___) continue;
        for (size_t t = 0; t < g[u].size(); ++t) {
            int v = g[u][t].to, w = g[u][t].w;
            if (dist[u][k] + w < dist[v][k]) {
                dist[v][k] = dist[u][k] + w;
                pq.push({dist[v][k], v, k});
            }
            if (___③___ && dist[u][k] < dist[v][k + 1]) {
                ___④___;
                pq.push({dist[v][k + 1], v, k + 1});
            }
        }
    }
    long long ans = INF;
    for (int k = 0; k <= K; ++k) ___⑤___;
    printf("%lld\n", ans);
    return 0;
}