实在是不知道错哪了，管理员还不给数据。

求大神调，赏 3 关。

/*******************************
| Author:  SunnyYuan
| Problem: P2829 大逃离
| OJ:      Luogu
| URL:     https://www.luogu.com.cn/problem/P2829
| When:    2023-10-28 16:37:22
| 
| Memory:  125 MB
| Time:    1000 ms
*******************************/

#include <bits/stdc++.h>

#define int long long

using namespace std;
using i64 = long long;

const int N = 5010, INF = 1e9;

vector<int> e[N], w[N];
set<int> s[N];

int n, m, k;
i64 dis[N][2];
bool vis[N][2];

struct node {
    i64 dis, type, id;
    bool operator>(const node b) const { return dis < b.dis; }
};

void dijkstra() {
    priority_queue<node, vector<node>, greater<node> > q;
    for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = INF;
    dis[1][0] = 0;
    q.push({0, 0, 1});

    while (q.size()) {
        i64 t = q.top().id, ty = q.top().type;
        q.pop();
        if (vis[t][ty]) continue;
        vis[t][ty] = true;

        for (int i = 0; i < e[t].size(); i++) {
            int to = e[t][i];
            if (to != 1 && to != n && s[to].size() < k) continue;
            if (dis[to][0] > dis[t][0] + w[t][i]) {
                dis[to][1] = dis[to][0];
                dis[to][0] = dis[t][0] + w[t][i];
                q.push({dis[to][0], 0, to});
                q.push({dis[to][1], 1, to});
            }
            if (dis[to][0] < dis[t][0] + w[t][i] && dis[to][1] > dis[t][0] + w[t][i]) {
                dis[to][1] = dis[t][0] + w[t][i];
                q.push({dis[to][1], 1, to});
            }
            if (dis[to][1] > dis[t][1] + w[t][i]) {
                dis[to][1] = dis[t][1] + w[t][i];
                q.push({dis[to][1], 1, to});
            }
        }
    }
}

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

    cin >> n >> m >> k;
    for (int i = 1, u, v, g; i <= m; i++) {
        cin >> u >> v >> g;

        e[u].push_back(v);
        e[v].push_back(u);
        w[u].push_back(g);
        w[v].push_back(g);

        s[u].insert(v);
        s[v].insert(u);
    }
    dijkstra();
    if (dis[n][1] >= INF / 2) cout << "-1\n";
    else cout << dis[n][1] << '\n';
    return 0;
}