#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e4+10,inf=2e9;
struct T{
	int x,d;
	friend bool operator <(T x,T y){
		return x.d>y.d;
	}
};
int n,m,k;
int d[maxn][110];
vector<pair<int,int>> e[maxn];
void bfs(){
	priority_queue<T> q;
	q.push({1,0});
	d[1][0]=0;
	while(q.size()){
		T now=q.top();q.pop();
		for(int i=0;i<e[now.x].size();i++){
			pair<int,int> nxt=e[now.x][i];
			if(d[nxt.first][(now.d+1)%k]>now.d+1){
				d[nxt.first][(now.d+1)%k]=now.d+1;
				if(now.d>=nxt.second) q.push({nxt.first,now.d+1});
				else{
					int d=(nxt.second-now.d+k-1)/k*k;
					q.push({nxt.first,now.d+d+1});
				}
			}
		}
	}
}
int main(){
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v,a;cin>>u>>v>>a;
		e[u].push_back({v,a});
	}
	for(int i=1;i<=n;i++) for(int j=0;j<k;j++) d[i][j]=inf;
	bfs();
	if(d[n][0]==inf) d[n][0]=-1;
	cout<<d[n][0]<<endl;
	return 0;
}