#include<bits/stdc++.h>
#define int long long
using namespace std;
struct st
{
    int nxt,a;
};
int n,m,k,arr[10001][1001];
vector<st> nt[10001];
int fcc(int x,int y)//函数调用需要极小时间，但不影响超时问题
{
    if(x<y)return (y-x+k-1)/k*k+x+1;
    return x+1;
}
signed main()
{
    ios::sync_with_stdio(false);
    memset(arr,0x0f0f,sizeof arr);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int x;st y;
        cin>>x>>y.nxt>>y.a;
        nt[x].push_back(y);
    }
    queue<int> l,t;
    l.push(1);t.push(0);
    while(!l.empty())
    {
        int x=l.front(),ti=t.front();
        l.pop();t.pop();
        if(ti>=arr[x][ti%k])continue;//这边每次等到放入队列再判断，太耗时
        arr[x][ti%k]=ti;
        for(int i=0;i<nt[x].size();i++)
        {
            int tl=fcc(ti,nt[x][i].a),ls=nt[x][i].nxt;
            t.push(tl);
            l.push(ls);
        }
    }
    if(arr[n][0]!=arr[0][0])cout<<arr[n][0]<<endl;
    else cout<<-1<<endl;
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct st
{
    int nxt,a;
};
int n,m,k,arr[10001][1001];
vector<st> nt[10001];
signed main()
{
    ios::sync_with_stdio(false);
    memset(arr,0x0f0f,sizeof arr);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int x;st y;
        cin>>x>>y.nxt>>y.a;
        nt[x].push_back(y);
    }
    queue<int> l,t;
    l.push(1);t.push(0);
    arr[1][0]=0;
    while(!l.empty())
    {
        int x=l.front(),ti=t.front();
        l.pop();t.pop();
        if(ti>arr[x][ti%k])continue;//保证时间为最小值
        for(int i=0;i<nt[x].size();i++)
        {
            int tl=(ti<nt[x][i].a?(nt[x][i].a-ti+k-1)/k*k+ti+1:ti+1),ls=nt[x][i].nxt;//修改函数，取消函数调用时间
            if(tl<arr[ls][tl%k])//若用时最小，则放入队列
            {
                arr[ls][tl%k]=tl;//之前此点此时的时间可能较大，但是由于上面continue掉了，无需弹出
                l.push(ls);
                t.push(tl);
            }
        }
    }
    if(arr[n][0]!=arr[0][0])cout<<arr[n][0]<<endl;
    else cout<<-1<<endl;
    return 0;
}