//考场0分代码
//求改为25分代码
#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010],n,m,k,minx;
int g;
void dfs(int x,int a){
	if(x%k==0&&x!=0){
		minx=min(minx,x);
		g=1;
		return;
	}
	for(int i=1;i<=m;i++){
		if(dp[a][m]-1<=x){
			dfs(x+1,m);
		}
	}
}
int main(){
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		dp[a][b]=c;
	}
	dfs(0,1);
	if(minx==0){
		cout<<-1;
	}
	else{
		cout<<minx;
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}