#include<bits/stdc++.h>
#define LL long long
#define int long long

using namespace std;

const int N=105;

int n,m,k;
vector<pair<int,int> > vec[N];

struct Martix {
	LL dp[N][N];
};

Martix operator*(const Martix& a,const Martix& b) {
	Martix newm;
	memset(newm.dp,63,sizeof(newm.dp));
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			for(int k=1;k<=n;++k) {
				newm.dp[i][j]=min(newm.dp[i][j],a.dp[i][k]+b.dp[k][j]);
			}
		}
	}
	return newm;
}

LL dp[2][N][N];

Martix ans,first;

Martix qpow(Martix now,int k) {
	if(k==1) return now;
	if(k&1) return qpow(now*now,k/2)*now;
	else return qpow(now*now,k/2);
}

signed main() {
	cin >> n >> m >> k;
	
	memset(dp,63,sizeof(dp));
	
	for(int i=1;i<=n;++i)
		dp[0][i][i]=dp[1][i][i]=0;
	
	int u,v,w;
	for(int i=1;i<=m;++i) {
		cin >> u >> v >> w;
		vec[u].push_back(make_pair(v,w));
		vec[v].push_back(make_pair(u,w));
		dp[0][u][v]=dp[1][u][v]=w;
	}
	
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				dp[0][i][j]=dp[1][i][j]=min(dp[0][i][k]+dp[0][k][j],dp[0][i][j]);
			}
		}
	}

	for(int u=1;u<=n;++u) {
		for(auto v_w:vec[u]) {
			auto v=v_w.first,w=v_w.second;
			for(int i=1;i<=n;++i) {
				for(int j=1;j<=n;++j) {
					dp[1][i][j]=min(dp[0][i][u]+dp[0][v][j]-w,dp[1][i][j]);
				}
			}
		}
	}
	
	if(k==0) {
		cout << dp[0][1][n];
		return 0;
	}
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			first.dp[i][j]=dp[1][i][j];
	
	ans=qpow(first,k);
	
	cout << ans.dp[1][n];
	
	return 0;
}

只有 $k=0$ 的点过了