#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) x.begin(), x.end()
typedef long long ll;
using namespace std;
const ll INF = ~(1LL << 63);
ll N, M, K;
bool walk(ll node, ll k, ll Q, ll C, vector<vector<array<ll, 2>>> &G, unordered_set<ll> &vis, vector<array<ll, 2>> &states) {
    ll i;
    vis.insert(node);
    if(vis.size() == N)
        return true;
    if(states[node][0] != -1 && (states[node][0] > k || (states[node][0] == k && states[node][1] >= Q)))
        return false;
    states[node][0] = k;
    states[node][1] = Q;
    for(const auto [nn, weight] : G[node]) {
        if(weight <= Q)
            walk(nn, k, Q - weight, C, G, vis, states);
        else if(weight <= C && k > 0)
            walk(nn, k - 1, C - weight, C, G, vis, states);
    }
    return vis.size() == N;
}
int main() {
    FastIO;
    ll i, n1, n2, C, bsmin, bsmax;
    cin >> N >> M >> K;
    vector<vector<array<ll, 2>>> G(N + 1);
    bsmin = INF;
    bsmax = 0;
    for(i = 0; i < M; i++) {
        cin >> n1 >> n2 >> C;
        G[n1].push_back({ n2, C });
        G[n2].push_back({ n1, C });
        bsmin = min(C, bsmin);
        bsmax += C;
    }
    while(bsmin != bsmax - 1) {
        C = bsmin + (bsmax - bsmin) / 2;
        for(i = 1; i <= N; i++) {
            unordered_set<ll> vis(N);
            vector<array<ll, 2>> states(N + 1, { -1, -1 });
            if(!walk(i, K, 0, C, G, vis, states)) {
                bsmin = C;
                goto next;
            }
        }
        bsmax = C;
        next:;
    }
    cout << bsmax << '\n';
    return 0;
}