#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5,M = 2e4 + 5;
int n,m,k,l,r,mid,tot,head[N],to[M],v[M],nxt[M],vis[N][110];
struct Node{int x,t;} tmp;
queue <Node> q;
void add(int x,int y,int z)
{
	tot++;
	to[tot] = y,v[tot] = z;
	nxt[tot] = head[x],head[x] = tot;
}
bool check(int s)
{
	memset(vis,0,sizeof(vis));
	vis[n][s % k] = 1;
	q.push((Node){n,s});
	for(int x,t,y;!q.empty();)
	{
		tmp = q.front(),q.pop();
		x = tmp.x,t = tmp.t;
		for(int i = head[x];i;i = nxt[i])
		{
			y = to[i];
			if(t - 1 < v[i] || vis[y][(t - 1) % k]) continue;
			vis[y][(t - 1) % k] = 1;
			q.push((Node){y,t - 1});
		}
	}
	return (vis[1][s % k] == 1);
}
int main()
{
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1,a,b,c;i <= m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(b,a,c);
	}
	l = -1,r = 2000000 / k;
	while(r - l > 1)
	{
		mid = (l + r) / 2;
		if(check(mid * k)) r = mid;
		else l = mid;
	}
	if(check(r * k)) printf("%d\n",r * k);
	else printf("-1\n");
	return 0;
}
/*
雨下整夜 我的爱溢出就像雨水
院子落叶 跟我的思念厚过一叠
几句是非 也不能把我的热情冷却
你出现在我诗的每一页
非常好题目 love from cyl 
*/