#include<iostream>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
int n,m,k,head[20005],nxt[20005],to[20005],cnt,dis[10005][105],a[20005],maxa;
void add(int u,int v,int w){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    a[cnt]=w;
    head[u]=cnt;
}
struct node{
    int id,dis,mod;
};
int solve(int x){
    queue<node> q;
    q.push((node){1,x,0});
    memset(dis,-1,sizeof(dis));
    dis[1][0]=x;
    while(!q.empty()){
        int u=q.front().id,x=q.front().mod;
        q.pop();
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(dis[u][x]>=a[i]&&dis[v][(x+1)%k]==-1){
                dis[v][(x+1)%k]=dis[u][x]+1;
                q.push((node){v,dis[u][x]+1,(x+1)%k});
            }
        }
    }
    return dis[n][0];
}
signed main(){
    //freopen("bus.in","r",stdin);
    //freopen("bus.out","w",stdout);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        maxa=max(maxa,w);
        add(u,v,w);
    }
    int l=0,r=maxa/k+1;
    int minn=-1;
    while(l<=r){
        int mid=(l+r)/2;
        int x=solve(mid*k);
        if(x!=-1){
            r=mid-1;
            minn=x;
        }else{
            l=mid+1;
        }
    }
    cout<<minn;
    return 0;
}

思路：二分+bfs