#include <bits/stdc++.h>
using namespace std;
#define debug
/*
感谢@×+b给我提供思路
优先队列版本
*/
struct edge{
    int v,a;
};
vector<edge> e[10005];
int n,m,k,u,v,a;
bool vis[10005][105];
struct nd{
    int x,step;
    bool operator<(const nd &a) const{return step<a.step;}
};
int bfs(){
    priority_queue<nd> apple;
    nd cur;
    apple.push({1,0});
    vis[1][0]=1;
    while (!apple.empty()){
        cur=apple.top();apple.pop();
        if ((!(cur.step%k))&&(cur.x==n)){
            return cur.step;
        }
        for (auto &&i : e[cur.x]){
            if (cur.step>=i.a){
                if (!vis[i.v][(cur.step+1)%k]){vis[i.v][(cur.step+1)%k]=1;apple.push({i.v,cur.step+1});}
            }else{
                int time=((i.a-cur.step+k-1)/k)*k+cur.step+1;
                if (!vis[i.v][time%k]){vis[i.v][time%k]=1;apple.push({i.v,time});}
            }
        }
    }
    return -1;
}
int main(){
    #ifndef debug
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    freopen("bus.err","w",stderr);
    #endif
    scanf("%d%d%d",&n,&m,&k);
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&a);
        e[u].push_back({v,a});
    }
    printf("%d",bfs());
    return 0;
}