Osumapping

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using lli=long long;
using pipii=pair<lli,pii>;
int n,m,t,st,en;
vector<pair<int,lli>> G[10010];
lli cal(){
    vector<vector<lli>> dis(n+10,vector<lli>(t,2e18));
    vector<vector<bool>> visited(n+10,vector<bool>(t,false));
    priority_queue<pipii,vector<pipii>,greater<pipii>> Q;
    dis[st][1%t]=0;
    Q.push({dis[st][1%t],{st,1%t}});
    while(!Q.empty()){
        int u=Q.top().second.first;
        int cnt=Q.top().second.second;
        Q.pop();
        if(visited[u][cnt]) continue;
        if(u==en&&cnt==0) return dis[u][cnt];
        visited[u][cnt]=1;
        for(auto x:G[u]){
            int to=x.first;
            lli w=x.second;
            if(!visited[to][(cnt+1)%t]&&dis[u][cnt]+w<dis[to][(cnt+1)%t]){
                dis[to][(cnt+1)%t]=dis[u][cnt]+w;
                Q.push({dis[to][(cnt+1)%t],{to,(cnt+1)%t}});
            }
        }
    }
    return -1;
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    scanf("%d%d",&st,&en);
    for(int i=0;i<m;i++){
        int u,v;
        lli w;
        scanf("%d%d%lld",&u,&v,&w);
        G[u].push_back({v,w});
    }
    cout << cal();
}