#include<algorithm>
#include <iostream>
#define maxN 301
#define Infi 10000000000


int varosszam, utszam, max_toltes;
long long T[maxN][maxN];
long long akku_graf[maxN][maxN];
long long T2[maxN][maxN];
long long X[maxN][maxN];


using namespace std;

void debug(long long A[maxN][maxN]) {
	for (int i = 1; i <= varosszam; i++)
	{
		for (int j = i + 1; j <= varosszam; j++)
		{
			//if (A[j][i] != A[i][j])cout << "SZIMETRIAVESZTESEG";
			cout << i << ", " << j << "\t" << A[i][j];
			cout << endl;
		}
	}
}

//Bekér két gráfot
//A-t módosítja
//					töltés					T2
void Szor(long long A[maxN][maxN], long long B[maxN][maxN]) {
	//X egy új gráf lesz
	for (int i = 1; i <= varosszam; i++)
		for (int j = 1; j <= varosszam; j++) {
			//Minden párra
			X[i][j] = Infi;

			//Ha i-bõl j-be szeretnénk eljutni,
			//úgy, hogy közben tölthetünk egyszer
			for (int u = 1; u <= varosszam; u++)
				X[i][j] = min(X[i][j], max(A[i][u], B[u][j]));
		}

	//Átírja A-t X értékeire
	for (int i = 1; i <= varosszam; i++)
		for (int j = 1; j <= varosszam; j++) {
			A[i][j] = X[i][j];
		}
}

int main() {
	//Cin tie null
	int kezdo, veg;
	long long a = 0, b, hossz;
	cin >> varosszam >> utszam >> max_toltes;

	//Felvesz valami gráfot.
	//Minden éle végtelen, kivéve ha önmagába visz
	//Akkor 0
	//1-tõl indexel!
	for (int i = 1; i <= varosszam; i++) {
		T[i][i] = 0;
		for (int j = i + 1; j <= varosszam; j++) {
			T[j][i] = Infi;
			T[i][j] = Infi;
		}
	}

	//Az elõzõleg felvett gráfnál beállítja az élek hosszát
	for (int i = 0; i < utszam; i++) {
		cin >> kezdo >> veg >> hossz;
		T[kezdo][veg] = hossz;
		T[veg][kezdo] = hossz;
	}

	//cout << "Sima beolvasas";
	//debug(T);
	//cout << endl << endl;


	//Máténak igaza volt valszeg, ez minimális utat keres
	//Minden élre megnézi, hogy lehet-e javítani egy köztes node-al
	for (int koztes_node = 1; koztes_node <= varosszam; koztes_node++)
		for (int i = 1; i <= varosszam; i++)
			for (int j = 1; j <= varosszam; j++)
				//Minden számhármason. Ez nagyon lassúnak tûnik
				T[i][j] = min(T[i][j], T[i][koztes_node] + T[koztes_node][j]);

	//debug(T);

	//T2 másolata T-nek
	for (int i = 1; i <= varosszam; i++) {
		//Önmagába 0
		akku_graf[i][i] = 0;
		T2[i][i] = 0;

		for (int j = i + 1; j <= varosszam; j++) {
			T2[i][j] = T[i][j];
			T2[j][i] = T[i][j];
			//Átmásolja a T-t
			akku_graf[i][j] = Infi;
			akku_graf[j][i] = Infi;
			//E-t meg felveszi végtelen élekkel
		}
	}

	/*while (max_toltes > 0) {

		if (max_toltes % 2 == 1) {
			Szor(akku_graf, T2);
		}


		Szor(T2, T2);

		max_toltes /= 2;
	}*/

	for (int i = 0; i < max_toltes; i++)
	{
		Szor(T2, T2);
	}

	for (int i = 1; i <= varosszam; i++)
		for (int j = 1; j <= varosszam; j++) {
			akku_graf[i][j] = T2[i][j];
		}

	//Maximális szükséges kapacitás kiválasztása
	for (int i = 1; i <= varosszam; i++)
		for (int j = i + 1; j <= varosszam; j++)
			a = max(a, akku_graf[i][j]);

	cout << a << "\n";
	return 0;
}