#include<bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<pair<int,int> >q;
vector<pair<int,int> >x[10005];
int ans[10005][105];
signed main(){
	memset(ans,0x7f,sizeof(ans));
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		x[a].push_back(make_pair(b,c));
	}
	ans[1][0]=k;
	q.push(make_pair(-k,1));
	while(!q.empty()){
		int now=q.top().second;
		int summ=-q.top().first;
		q.pop();
		if(summ%k==0&&now==n){
			cout<<summ;
			return 0;
		}
		for(int i=0;i<x[now].size();i++){
			if(summ>=x[now][i].second&&summ+1<ans[x[now][i].first][(summ+1)%k]){
				ans[x[now][i].first][(summ+1)%k]=summ+1;
				q.push(make_pair(-(summ+1),x[now][i].first));
			}
			else if(summ<x[now][i].second){
				int got=x[now][i].second/k*k+summ%k;
				if(got<x[now][i].second)got+=k;
				if(got+1<ans[x[now][i].first][(got+1)%k]){
					ans[x[now][i].first][(got+1)%k]=got+1;
					q.push(make_pair(-(got+1),x[now][i].first));
				}
			}
		}
	}
	cout<<-1;
    return 0;
}