#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e4+7, M=2e4+7, K=107;
int n, m, k;
int dis[N][K];
int head[N], nxt[M], to[M], a[M], tot=0;
struct node{
	int d, x, y;
	node(){}
	node(int d, int x, int y):d(d), x(x), y(y){}
};
bool operator >(node x, node y){
	return x.d>y.d;
}
priority_queue<node, vector<node>, greater<node> > q;
void add(int x, int y, int z){
	tot++;
	nxt[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	a[tot]=z;
}
void dij(int x){
	memset(dis, 0x3f, sizeof(dis));
	dis[x][0]=0;
	q.push(node(0, x, 0));
	while(q.size()){
		node now=q.top();q.pop();
		if(now.d>dis[now.x][now.y])
			continue;
		for(int i=head[now.x];i;i=nxt[i]){
			int v=to[i], ndis=now.d+1, ty=ndis%k;
			if(ndis<a[i])
				ndis+=(a[i]-ndis+k-1)/k*k;
			if(ndis<dis[v][ty]){
				dis[v][ty]=ndis;
				if(v==n && ty==0){
					return;
				}
				q.push(node(ndis, v, ty));
			}
		}
	}
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int x, y, z;
		cin>>x>>y>>z;
		add(x, y, z);
	}
	dij(1);
	cout<<dis[n][0]<<endl;
	return 0;
}

#2 #8 #9 #10 #21 WA