#include<bits/stdc++.h>
using namespace std;
long long cnt;
struct eg{
    long long v,w;
};
struct ge{
    long long a,b,c;
};
vector<eg>g[10005];
vector<ge>ti;
long long n,m,k,ans=0x3f3f3f3f;
void dfs(long long u,long long t,long long r,long long j){
    if(u==n){
        if(t%k==0){
            ans=t;
            ti.push_back({t,r,j});
        }
        return ;
    }
    for(int i=0;i<g[u].size();i++){
        eg v=g[u][i];
        if(v.w>t && v.w-t>r-j)
            r=v.w,j=t;
        dfs(v.v,t+1,r,j);
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    dfs(1,0,0,0);
    if(ans==0x3f3f3f3f){
        cout<<-1;
        return 0;
    }
    ans=0x3f3f3f3f;
    for(int i=0;i<ti.size();i++){
        ge q=ti[i];
        ans=min(ans,(q.b-q.c+k-1)/k*k+q.a);
    }
    cout<<ans;
    return 0;
}