#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#define int long long
using namespace std;
const int N=2e5 + 7;
int n, m, k;
const int inf = 1e18;
struct Node{
    int v, w;
};
vector<Node>edge[N];
priority_queue<pair<int, int>>q;
int vis[N];
int d[N];
void Dijkstra(int s) {
    memset(d, 0x3f3f3f, sizeof(d));
    d[s] = 0;
    q.push({ 0,s });
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (vis[u])continue;
        vis[u] = 1;
        for (auto ed : edge[u]) {
            int v = ed.v;
            int w = ed.w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({ -d[v],v });
            }
        }
    }
}
void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edge[u].push_back({ v,w });
        edge[v].push_back({ u,w });
        for (int j = 1; j <= k; j++) {//k层
            //上一层 链接 下一层
            edge[u + (j - 1) * n].push_back({ v + j * n,w/2 });
            edge[v + (j - 1) * n].push_back({ u + j * n,w/2 });
            //这一层
            edge[u + j * n].push_back({ u + j * n,w });
            edge[u + j * n].push_back({ u + j * n,w });
        }
    }
    for (int i = 1; i <= k; i++) {
        edge[n + (i - 1) * n].push_back({ n + i * n,0 });
    }
    Dijkstra(1);
    cout << d[n + k * n] << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    solve();
}

想不明白了 谢谢各位佬