#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<map<int, int>> gg(N + 1);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		gg[a].insert({b, c});
		gg[b].insert({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++) {
			auto g = gg;
			vector<int> v(N + 1);
			vector<vector<int>> l(K + 1);
			v[i] = true;
			l[0].push_back(i);
			for (int j = 0; j < K; j++) {
				vector<int> a(N + 1, -1);
				auto dfs = [&](auto dfs, int i) -> void {
					for (auto [k, c] : g[i]) {
						g[k].erase(i);
						if (!v[k] && a[k] < a[i] - c) {
							a[k] = a[i] - c;
							l[j + 1].push_back(k);
							dfs(dfs, k);
						}
					}
				};
				for (int k : l[j]) {
					a[k] = m;
					dfs(dfs, k);
				}
				for (int k : l[j + 1]) {
					v[k] = true;
				}
			}
			if (count(v.begin(), v.end(), 1) < N) {
				ok = false;
				break;
			}
		}
		if (ok) {
			h = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l << '\n';
	return 0;
}