#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<vector>
#include<queue>

using namespace std;

const int N=1e4+10,K=100+10;

int n,m,k;
int dis[N][K];
bool vis[N][K];

struct Edge{
	int to,a;
};

vector<Edge>G[N];

struct Node{
	int u,t;
	bool operator>(const Node &tmp)const{
		return t>tmp.t;
	}
};

priority_queue<Node,vector<Node>,greater<Node> >pq;

void Dij(int st,int tt){
	
	memset(dis,0x3f,sizeof(dis));
	dis[st][tt]=0;
	pq.push((Node){st,tt});
	while(!pq.empty()){
		Node tmp=pq.top();pq.pop();
		int u=tmp.u,t=tmp.t;
		if(vis[u][t%k])continue;
		if(u==n&&t==0)return ;
		vis[u][t%k]=true;
		for(int i=0;i<G[u].size();i++){
			Edge e=G[u][i];
			int v=e.to,mn=e.a;
			int tmp=t+1,ttt=(t+1)%k;
			if(vis[v][ttt])continue;
			int td=dis[v][ttt];
			if(tmp>=mn)
				dis[v][ttt]=min(dis[v][ttt],tmp);
			else{
				int c=mn-tmp;
				if(c%k==0)
					dis[v][ttt]=min(dis[v][ttt],mn);
				else
					dis[v][ttt]=min(dis[v][ttt],tmp+(c/k+1)*k);
			}
			if(dis[v][ttt]!=td)
				pq.push((Node){v,dis[v][ttt]});
		}
	}
	return ;
	
}

signed main(){
	
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,u,v,a;i<=m;i++){
		scanf("%d%d%d",&u,&v,&a);
		G[u].push_back((Edge){v,a});
	}
	Dij(1,0);
	if(dis[n][0]!=0x3f3f3f3f)
		printf("%d\n",dis[n][0]);
	else
		printf("-1\n");
	return 0;
	
}
/*
5 5 1
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1
*/