#include<bits/stdc++.h>
#define int long long
using namespace std;
int floyd[110][110];
struct node{
	int u,v,w;
}e[2510];
struct node1{
	int c[110][110],bc;
};
void init(node1 x){
	for(int i=1;i<=x.bc;i++){
		for(int j=1;j<=x.bc;j++){
			x.c[i][j]=INT_MAX;
		}
	}
}
node1 operator*(node1 x,node1 y){
	node1 c;
	init(c);
	c.bc=x.bc;
	for(int k=1;k<=c.bc;k++){
		for(int i=1;i<=c.bc;i++){
			for(int j=1;j<=c.bc;j++){
				c.c[i][j]=min(c.c[i][j],x.c[i][k]+y.c[k][j]);
			}
		}
	}
	return c;
}
node1 quick_pow(node1 x,int k){
	node1 c,d;
	c.bc=x.bc;
	d=x;
	for(int i=1;i<=x.bc;i++){
		for(int j=1;j<=x.bc;j++){
			c.c[i][j]=floyd[i][j];
		}
	}
	while(k){
		if(k&1){
			c=c*d;
		}
		d=d*d;
		k>>=1;
	}
	return c;
}

signed main(){
//	freopen("short.in","r",stdin);
//	freopen("short.out","w",stdout);
	int n,m,k;
	cin>>n>>m>>k;
	memset(floyd,0x3f3f3f3f3f3f3f3f,sizeof(floyd));
	for(int i=1;i<=n;i++){
		floyd[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
		floyd[e[i].u][e[i].v]=e[i].w;
	}
	for(int kk=1;kk<=n;kk++){
		for(int i=1;i<=n;i++){
			if(i!=kk){
				for(int j=1;j<=n;j++){
					if(j!=kk&&i!=j){
						floyd[i][j]=min(floyd[i][j],floyd[i][kk]+floyd[kk][j]);
					}
				}
			}
		}
	}
	if(k){
		node1 a;
		a.bc=n;
//		init(a);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				a.c[i][j]=floyd[i][j];
			}
		}
		for(int kk=1;kk<=m;kk++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					a.c[i][j]=min(a.c[i][j],floyd[i][e[kk].u]+floyd[e[kk].v][j]-e[kk].w);
				}
			}
		}
		cout<<quick_pow(a,k).c[1][n];
	}
	else{
		cout<<floyd[1][n];
	}
	return 0;
}

RT.调了好久了，哪位dalao来帮一帮