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

#define int long long
#define double long double

#define pii pair<int, int>

template<typename T>
using min_priority_queue = std::priority_queue<T, vector<T>, greater<T>>;

template<typename T, typename U>
bool ckmin(T& a, const U& b) {
	return b < a ? a = b, true : false;
}

#define A (int)1e15
#define B (int)1e18

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 = A;
	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, B);
			min_priority_queue<pii> pq;
			pq.emplace(0, i);
			v[i] = 0;
			while (!pq.empty()) {
				auto j = pq.top();
				pq.pop();
				if (j.first > v[j.second]) {
					continue;
				}
				for (pii p : g[j.second]) {
					int c = v[j.second] + p.second;
					if (p.second > m) {
						continue;
					}
					if (c % A >= m) {
						c -= c % A;
						c += A + p.second;
					}
					if (ckmin(v[p.first], c)) {
						pq.emplace(v[p.first], p.first);
					}
				}
			}
			for (int j = 1; j <= N; j++) {
				if (v[j] / A > K) {
					goto bad;
				}
			}
		}
		if (ok) {
			h = m;
		}
		else {
		bad:
			l = m + 1;
		}
	}
	cout << l << '\n';
	return 0;
}