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

#define int long long
#define double long double

#define pii pair<int, int>

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("be2.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int N, M, K;
	cin >> N >> M >> K;
	vector<vector<pii>> g(N + 1);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	int l = 0, h = 1e15;
	while (l < h) {
		int m = (l + h) / 2;
		// m possible?
		bool ok = true;
		for (int i = 1; i <= N; i++) {
			vector<int> v(N + 1);
			vector<set<int>> l(K + 1);
			v[i] = 1;
			l[0].insert(i);
			for (int j = 0; j < K; j++) {
				auto dfs = [&](auto dfs, int i, int r) -> void {
					for (auto [k, c] : g[i]) {
						if (v[k] == 0 && r >= c) {
							v[k] = 1;
							l[j + 1].insert(k);
							dfs(dfs, k, r - c);
						}
					}
				};
				for (int k : l[j]) {
					dfs(dfs, k, m);
				}
			}
			if (count(v.begin(), v.end(), 1) < N) {
				ok = false;
				break;
			}
		}
		if (ok) {
			h = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l << '\n';
	return 0;
}