#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct str  { ll v,a; };

struct edge  { ll now,mod; };

vector<str>vec[10010];

queue<edge>q;

ll n,m,k,dp[10010][110],flag[10010][110];

int main()
{
	cin>>n>>m>>k;
	for(ll i=0;i<=n;i++)  for(ll j=0;j<=k;j++)  dp[i][j]=1e18;
	for(ll i=1;i<=m;i++)
	{
		ll u,v,a;cin>>u>>v>>a;
		vec[u].push_back({v,a});
	}
	q.push({1,0});  dp[1][0]=0;  flag[1][0]=1;
	while(!q.empty())
	{
		edge x=q.front();q.pop();
		ll now=x.now,mod=x.mod;  flag[now][mod]=0;
		for(ll i=0;i<vec[now].size();i++)
		{
			ll nex=vec[now][i].v,nedp=dp[now][mod],modd=mod+1;if(modd==k)  { modd=0;nedp++; }
			while(nedp*k+modd<vec[now][i].a)  nedp+=1; 
			if(nedp<dp[nex][modd])
			{
				dp[nex][modd]=nedp;
				if(!flag[nex][modd])  { q.push({nex,modd});flag[nex][modd]=1; }
			}
		}
	}
	if(dp[n][0]>=1e12)  cout<<-1;
	else  cout<<dp[n][0]*k;
	return 0;
} 

WA #8,9,10