#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, G[101][101];
void walk(ll node, ll k, ll Q, ll C, vector<bool> &vis, vector<array<ll, 2>> &states) {
    ll i;
    vis[node] = true;
    if(states[node][0] != -1 && (states[node][0] > k || (states[node][0] == k && states[node][1] > Q)))
        return;
    states[node][0] = k;
    states[node][1] = Q;
    for(i = 1; i <= N; i++) {
        if(!G[node][i])
            continue;
        if(G[node][i] <= Q)
            walk(i, k, Q - G[node][i], C, vis, states);
        else if(G[node][i] <= C && k > 0)
            walk(i, k - 1, C - G[node][i], C, vis, states);
    }
}
int main()
{
    FastIO;
    ll i, n1, n2, C, bsmin, bsmax;
    cin >> N >> M >> K;
    bsmin = INF;
    bsmax = 0;
    for(i = 0; i < M; i++) {
        cin >> n1 >> n2 >> C;
        G[n1][n2] = C;
        G[n2][n1] = C;
        bsmin = min(C, bsmin);
        bsmax += C;
    }
    while(bsmin != bsmax - 1) {
        C = bsmin + (bsmax - bsmin) / 2;
        for(i = 1; i <= N; i++) {
            vector<bool> vis(N + 1, false);
            vector<array<ll, 2>> states(N + 1, { -1, -1 });
            walk(i, K, 0, C, vis, states);
            if(!all_of(vis.begin() + 1, vis.end(), [](auto a) { return a; })) {
                bsmin = C;
                goto next;
            }
        }
        bsmax = C;
        next:;
    }
    cout << bsmax << '\n';
    return 0;
}