#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int MAXN = 10005;
const int MAXK = 25;

struct Edge {
    int to;
    ll cost;
};

int N, M, K;
vector<Edge> adj[MAXN];
ll dist[MAXN][MAXK];

void dijkstra() {
    // priority_queue sap xep theo cost (lon nhat o dau)
    // nen dung greater de co cost nho nhat len dau
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;

    // Khoi tao du lieu
    for (int i = 1; i <= N; ++i)
        for (int k = 0; k <= K; ++k)
            dist[i][k] = INF;

    dist[1][0] = 0;
    pq.push({0, 1, 0}); // cost, node, pipes_used

    while (!pq.empty()) {
        auto [d, u, pipes_used] = pq.top(); pq.pop();

        // Neu duong di hien tai dai hon duong da luu thi bo qua
        if (d > dist[u][pipes_used]) continue;

        for (auto [v, w] : adj[u]) {
            // Truong hop 1: Khong su dung ong dan (chi phi goc)
            if (dist[v][pipes_used] > dist[u][pipes_used] + w) {
                dist[v][pipes_used] = dist[u][pipes_used] + w;
                pq.push({dist[v][pipes_used], v, pipes_used});
            }

            // Truong hop 2: Su dung ong dan (chi phi = 0)
            // Chi duoc phep neu so ong da su dung < K
            if (pipes_used < K && dist[v][pipes_used + 1] > dist[u][pipes_used]) {
                dist[v][pipes_used + 1] = dist[u][pipes_used];
                pq.push({dist[v][pipes_used + 1], v, pipes_used + 1});
            }
        }
    }

    ll ans = INF;
    for (int i = 0; i <= K; ++i) {
        ans = min(ans, dist[N][i]);
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen("gaspipe.inp", "r")) {
        freopen("gaspipe.inp", "r", stdin);
        freopen("gaspipe.out", "w", stdout);
    }

    cin >> N >> M >> K;
    for (int i = 0; i < M; ++i) {
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        // Neu de bai la do thi co huong, dong nay chi duoc su dung cho canh u->v
        // De bai anh huong den chieu duong di tu 1 den N, nhung dau vao co the co 2 chieu
        // De an toan cho bai toan duong di, ta them canh nguoc lai neu can
        // Tuy nhien, trong bai nay, chi them u->v la du (va dung) cho duong di tu 1 den N
        // Neu de bai yeu cau duyet ca 2 chieu (do thi vo huong), them:
        adj[v].push_back({u, w}); 
    }
    dijkstra();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    long long cost;
};

struct State {
    long long cost;
    int node;
    int pipes_used;
    bool operator>(const State &other) const {
        return cost > other.cost;
    }
};

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

    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<Edge>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c}); // Giả sử đồ thị vô hướng
    }

    const long long INF = 1e18;
    // dist[node][pipes_used]
    vector<vector<long long>> dist(n + 1, vector<long long>(k + 1, INF));
    priority_queue<State, vector<State>, greater<State>> pq;

    dist[1][0] = 0;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        int u = cur.node;
        long long c = cur.cost;
        int used = cur.pipes_used;

        if (c > dist[u][used]) continue;

        for (auto &edge : adj[u]) {
            int v = edge.to;
            long long w = edge.cost;

            // Truong hop 1: Khong su dung ong
            if (dist[v][used] > c + w) {
                dist[v][used] = c + w;
                pq.push({dist[v][used], v, used});
            }

            // Truong hop 2: Su dung ong
            if (used < k && dist[v][used + 1] > c) {
                dist[v][used + 1] = c;
                pq.push({c, v, used + 1});
            }
        }
    }

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

    return 0;
}