我的做法在反图上从 $1$ 开始跑最短路过了。

il void Solve()
{
  int n,m,K,p;rd(n),rd(m),rd(K),rd(p);
  ve<ve<pii>>G(n),nG(n);
  for(int u,v,w;m--;rd(u),rd(v),rd(w),--u,--v,G[u].pb(v,w),nG[v].pb(u,w));
  auto Dij=[&](int S,auto&G,auto&dis)
  {
    dis.assign(n,inf);
    priority_queue<pii,ve<pii>,greater<>>hp;
    for(hp.ep(dis[S]=0,S);hp.size();) {
      auto[_,u]=hp.top();
      hp.pop();
      if(_>dis[u]) continue;
      for(auto[v,w]:G[u]) if(cn(dis[v],_+w)) hp.ep(dis[v],v);
    }
  };
  ve<int>dis(n),ndis(n);
  Dij(0,G,dis),Dij(n-1,nG,ndis);
  ve<int>vis(n,-1),S;
  auto chk=[&](int u){return dis[u]+ndis[u]<=dis[n-1]+K;};
  function<int(int,int)>dfs=[&](int u,int c)->int
  {
    if(vis[u]==c) {
      for(;S.size()&&S.back()!=u;S.pop_back()) {
        if(chk(S.back())) return 1;
      }
      return chk(u);
    }
    S.pb(u),vis[u]=c;
    int flg=0;
    for(auto[v,w]:G[u]) if(!w&&dfs(v,c)) {
      flg=1;
      break;
    }
    if(S.size()&&S.back()==u) S.pop_back();
    return flg;
  };
  for(int i=0;i<n;++i) if(!~vis[i]&&dfs(i,i)) return wrt(-1,'\n');
  auto Add=[&](int&x,int y){(x+=y)<p||(x-=p);};
  ve<ve<int>>f(K+1,ve<int>(n));
  auto ord=[&]
  {
    ve<int>d(n),ord;
    int t=0;
    for(int u=0;u<n;++u) for(auto[v,w]:G[u]) if(dis[v]==dis[u]+w) ++d[v];
    queue<int>q;
    for(int u=0;u<n;++u) if(!d[u]) q.ep(u);
    for(;q.size();) {
      int u=q.front();
      ord.pb(u),q.pop();
      for(auto[v,w]:G[u]) if(dis[v]==dis[u]+w&&!--d[v]) q.ep(v);
    }
    return ord;
  }();
  assert(ord.size()&&ord[0]==0);
  f[0][0]=1;
  for(int k=0;k<=K;++k) for(int u:ord) {
    for(auto[v,w]:G[u]) {
      int d=dis[u]+k+w-dis[v];
      if(d<=K) Add(f[d][v],f[k][u]);
    }
  }
  int ans=0;
  for(int k=0;k<=K;++k) Add(ans,f[k][n-1]);
  wrt(ans,'\n');
  return;
}