// 分层图最短路 Dijkstra 算法 O(nk*log(nk))
#include<bits/stdc++.h>
#define pli pair<long long,int>
using namespace std;

const int N=10005,M=105;
vector<pli> e[N];
int n,m,k;
long long d[N][M]; //d[u,j]表示到达u点的时间mod k的值为j的最短花费时间
bool vis[N][M];

void dijkstra(){
  memset(d,0x3f,sizeof(d)); d[1][0]=0;
  priority_queue<pli,vector<pli>,greater<pli> > q;
  q.push({0,1});
  while(!q.empty()){
    auto [p,u]=q.top(); q.pop();
    if(vis[u][p%k]) continue; vis[u][p%k]=1;
    for(auto [v,w]:e[u]){
      int t=(p>=w)?p:(w-p+k-1)/k*k+p; //到u点的合法的最优时间
      if(d[v][(t+1)%k]>t+1){
        d[v][(t+1)%k]=t+1;
        q.push({t+1,v});
      }
    }
  }
}
int main(){
  scanf("%d%d%d",&n,&m,&k);
  for(int i=0,u,v,w;i<m;i++){
    scanf("%d%d%d",&u,&v,&w);
    e[u].push_back({v,w});
  }
  dijkstra();
  printf("%lld\n",vis[n][0]?d[n][0]:-1);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
const int N = 1e4 + 10, K = 105;
LL n, m, k, d[N][K]; bool v[N][K];
vector<PII> G[N];
void dijkstra()
{
    memset(d, 0x3f, sizeof(d)); d[1][0] = 0;
    memset(v, 0, sizeof(v));
    priority_queue<PII, vector<PII>, greater<PII>> Q; Q.push({0, 1});
    while (!Q.empty())
    {
        LL x = Q.top().second, t = Q.top().first; Q.pop();
        if (v[x][t % k]) continue;
        v[x][t % k] = 1;
        for (auto i : G[x])
        {
            LL y = i.first, w = i.second;
            LL tt = t + 1 + (t < w ? (w - t + k - 1) / k * k : 0);
            if (d[y][tt % k] > tt)
            {
                d[y][tt % k] = tt;
                Q.push({tt, y});
            }
        }
    }
}
int main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for (LL i = 1, x, y, w; i <= m; i++) scanf("%lld%lld%lld", &x, &y, &w), G[x].push_back({y, w});
    dijkstra();
    printf("%lld\n", (v[n][0] == 1) ? d[n][0] : -1);
    return 0;
}