// Problem: P4822 [BJWC2012] 冻结
// URL: https://www.luogu.com.cn/problem/P4822
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// OvO！

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 55;
const int INF = 0x3f3f3f3f;

int n, m, k;
vector<pair<int, int>> adj[MAX];
int dis[MAX][MAX];

struct Nde {
    int c, u, k; // c: cost, u: city, k: cards used
    bool operator>(const Nde& o) const {
        return c > o.c;
    }
};



void dijk() {
    memset(dis, 0x3f, sizeof(dis));
    dis[1][0] = 0;

    priority_queue<Nde, vector<Nde>, greater<Nde>> pq;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        Nde cur = pq.top();
        pq.pop();

        int c = cur.c;
        int u = cur.u;
        int k_ = cur.k;

        if (c > dis[u][k_]) {
            continue;
        }

        for (auto& edg : adj[u]) {
            int v = edg.first;
            int w = edg.second;

            // 不使用卡片
            if (dis[v][k_] > c + w) {
                dis[v][k_] = c + w;
                pq.push({dis[v][k_], v, k_});
            }

            // 使用卡片
            if (k_ < k && dis[v][k_ + 1] > c + w / 2) {
                dis[v][k_ + 1] = c + w / 2;
                pq.push({dis[v][k_ + 1], v, k_ + 1});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijk();

    int ans = INF;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dis[n][i]);
    }

    cout << ans << endl;

    return 0;
}