求赞！

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const ll N=10010,K=110;
priority_queue<PLL,vector<PLL>,greater<PLL>> q;
vector<PLL> e[N];
ll n,m,k,dis[N][K];
bool vis[N][K];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    while(m--) {
        ll u,v,a;
        cin>>u>>v>>a;
        e[u].push_back({v,a});
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;
    q.push({0,1});
    while(!q.empty()) {
        ll u=q.top().second,t=q.top().first;
        q.pop();
        if(vis[u][t%k]) continue;
        vis[u][t%k]=1;
        for(PLL x:e[u]) {
            ll v=x.first,w=x.second;
            if(t>=w) w=t;
            else w=(w-t+k-1)/k*k+t;
            if(dis[v][(w+1)%k]>w+1) {
                dis[v][(w+1)%k]=w+1;
                q.push({dis[v][(w+1)%k],v});
            }
        }
    }
    if(dis[n][0]==0x3f3f3f3f3f3f3f3f) cout<<-1;
    else cout<<dis[n][0];
    return 0;
}