#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long ans[20001][201];
bool bj[20001][201];
//--------------------------------------图
struct Node{
int to;
long long w;
};
vector <Node> a[30001];
//--------------------------------------堆
struct Node2{
int now;
long long w;
};
Node2 b[2000000];
int tot=0;
void work(int x){
if(x/2>=1&&b[x].w<b[x/2].w){
swap(b[x],b[x/2]);
work(x/2);
}
}
void work1(int x){
if(b[x*2].w<b[x*2+1].w&&x*2+1<=tot&&b[x*2].w<b[x].w){
swap(b[x*2],b[x]);
work1(x*2);
}
else if(x*2+1<=tot&&b[x*2+1].w<b[x].w){
swap(b[x*2+1],b[x]);
work1(x*2+1);
}
else if(x*2+1>tot&&x*2<=tot&&b[x*2].w<b[x].w){
swap(b[x*2],b[x]);
work1(x*2);
}
else{
return;
}
}
//----------------------------------------------------bfs
void bfs(int x,long long js){
if(bj[x][js%k+1]){
return;
}
bj[x][js%k+1]=1;
ans[x][js%k+1]=js;
long long awa=0;
for(auto it:a[x]){
b[++tot]={it.to,js+max((it.w-js+k-1)/k,awa)*k+1};
work1(tot);
}
}
//------------------------------------------------------------
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[u].push_back({v,w});
}
b[++tot]={1,0};
ans[n][1]=-1;
while(tot!=0){
bfs(b[1].now,b[1].w);
swap(b[1],b[tot]);
tot--;
work1(1);
}
cout<<ans[n][1];
return 0;
}