谢谢有心人了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=(int)1<<60,maxn=10005;
int n,m,K,cnt,lnk[maxn],dis[maxn][105];
bool vis[maxn][105];
struct edge{
	int to,nxt,w;
}e[2*maxn];
struct BNS{
    int u,i,d;
    bool operator<(const BNS &B)const{return d>B.d;}
};priority_queue<BNS>que;
int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f^=!(ch^'-'),ch=getchar();
	while( isdigit(ch)) ret=(ret<<3)+(ret<<1)+(ch&15),ch=getchar();
	if(!f) ret=-ret; return ret;
}
void add_e(int x,int y,int z){e[++cnt]=(edge){y,lnk[x],z};lnk[x]=cnt;}
void DIJ_HEAP(){
    memset(dis,0x3f,sizeof(dis));
    que.push((BNS){1,0,0}),dis[1][0]=0;
    while(!que.empty()){
        int x=que.top().u,t=que.top().i;que.pop();
        if(vis[x][t]) continue;
        vis[x][t]=1;
        for (int j=lnk[x];j;j=e[j].nxt){
            int y=e[j].to,w=e[j].w,T=dis[x][t],k=(t+1)%K;
            if(T<w) T+=(w-T+K-1)/K*K;
            if(dis[y][k]>T+1) que.push((BNS){y,k,dis[y][k]=T+1});
        }
    }
}
signed main() {
//  freopen("bus.in","r",stdin);
// 	freopen("bus.out","w",stdout);
    n=read(),m=read(),K=read();
    for(int i=1;i<=m;i++){int x=read(),y=read(),z=read();add_e(x,y,z);}
    DIJ_HEAP();
    if(dis[n][0]==INF) dis[n][0]=-1; printf("%d\n",dis[n][0]);
    return 0;
}