#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
struct edge
{
    ll q,z,xg,a;
}ed[20005];
ll n,m,k,dd[10005],db=1,jl[10005][105],bj[10005][105];
struct sdl
{
    ll b,mm;
    bool operator<(const sdl &c)const{
        return jl[c.b][c.mm]<jl[b][mm];
    }
    bool operator>(const sdl &c)const{
        return jl[c.b][c.mm]<jl[b][mm];
    }
};

void fjq(ll a,ll b,ll c){
    ed[db].a=c,ed[db].q=a,ed[db].z=b,ed[db].xg=dd[a],dd[a]=db++;
}
priority_queue<sdl>q;
void dj(){
    sdl a;
    a.b=1,a.mm=0;
    q.push(a);
    while(!q.empty()){
        ll root=q.top().b,ms=q.top().mm;
        q.pop();
        for(ll i=dd[root];i;i=ed[i].xg){
            ll to=ed[i].z;
            if(ed[i].a>jl[root][ms]){
                jl[to][(ms+1)%k]=min(jl[to][(ms+1)%k],jl[root][ms]+1+
                ((ed[i].a-jl[root][ms])/k)*k+(((ed[i].a-jl[root][ms])%k)?k:0));
                
            }
            else jl[to][(ms+1)%k]=min(jl[to][(ms+1)%k],jl[root][ms]+1);
            
            if(!bj[to][(ms+1)%k]){
                cout<<root<<' '<<to<<' '<<ms<<' '<<jl[to][(ms+1)%k]<<' '<<jl[root][ms]<<endl;
                bj[to][(ms+1)%k]=1;
                a.b=to,a.mm=(ms+1)%k;
                q.push(a);
            }
        }
    }
}
int main(){
    // freopen("P9751_4.in","r",stdin);
    scanf("%lld%lld%lld",&n,&m,&k);
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<k;j++){
            jl[i][j]=1145141919810;
        }
    }
    ll aa,bb,cc;
    for(ll i=1;i<=m;i++){
        scanf("%lld%lld%lld",&aa,&bb,&cc);
        fjq(aa,bb,cc);
    }
    jl[1][0]=0;
    dj();
    if(jl[n][0]==1145141919810)printf("-1");
    else printf("%lld",jl[n][0]);
    return 0;
}

wa的数据：

in
9 15 97
1 1 990149
6 4 393083
4 7 171280
6 7 635660
8 6 123113
1 2 384925
6 7 507533
8 6 416969
3 4 975110
2 5 575466
2 4 72458
7 9 923003
5 3 590414
4 8 733761
7 5 440313
out
923052

我的输出：

975141