#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using S = pair<ll, ll>;

const ll INF = 1e12;
const int MAXN = 101;

int n, m, k;

vector<pair<int, ll>> g[MAXN];

S step(S x, ll w, ll cap) {
    if (w > cap) return {INF, INF};
    S res = x;
    res.second += w;
    if (res.second > cap) {
        res.first += 1;
        res.second = w;
    }
    return res;
}

bool f(ll cap) {
    for (int i = 1; i <= n; i++) {
        priority_queue<pair<S, int>, vector<pair<S, int>>, greater<pair<S, int>>> pq;
        vector<S> dist(n+1, {INF, INF});
        dist[i] = {0, cap};
        pq.push({{0, cap}, i});
        while (!pq.empty()) {
            auto [s, u] = pq.top();
            pq.pop();
            if (dist[u] != s) continue;
            for (auto [v, w] : g[u]) {
                S d = step(s, w, cap);
                if (d < dist[v]) {
                    dist[v] = d;
                    pq.push({d, v});
                }
            }
        }
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            cnt += dist[j].first <= k;
        }
        if (cnt < n) return 0;
    }
    return 1;
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    ll lo = 1, hi = INF;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (f(mid)) hi = mid;
        else lo = mid+1;
    }
    cout << lo << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}