1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a; i<=b; ++i)
#define pb push_back
#define fi first 
#define se second 

constexpr ll MAX_N=7e3+14, MAX_M=7e3+14, MAX_K=7e3+14, INF=6e16;
struct jellyS{
    ll m, val;
};
ll N, K, M, mrg[MAX_M][MAX_M], tmp[MAX_M], dp[MAX_M][MAX_M];
vector<jellyS> jelly[MAX_K];
void Input(){
    ll k, m, val;
    cin>>N>>K>>M;
    FOR(i,0,N-1){
        cin>>k>>m>>val;
        jelly[k].pb({m,val});
    }
}
void SetDp(){
    FOR(i,0,M) FOR(j,1,M) mrg[i][j]=INF;
    mrg[0][0]=0;
    FOR(kk, 1, K){
        FOR(i,0,M) FOR(j,0,M) dp[i][j]=INF; 
        dp[0][0]=0;
        FOR(i,1,M){
            FOR(j,0,M-1) tmp[j]=INF;
            for(auto cE:jelly[kk]){//seting dp
                FOR(j,0,M-1){
                    dp[i][j]=min(dp[i][j],dp[i-1][(M+j-cE.m)%M]+cE.val);
                }
            }
            FOR(j,0,M-1){ //merging
                if(dp[i][j]==INF) continue;
                FOR(jj,0,M-1) tmp[jj]=min(tmp[jj],mrg[i][(M+jj-j)%M]+dp[i][j]);
            }
            FOR(jj,0,M-1) mrg[i][jj]=tmp[jj];
        }
    }
}
void Print(){
    ll cRes;
    FOR(i,0,M-1){
        cRes=INF;
        FOR(j,0,M) cRes=min(cRes, mrg[j][i]);
        if(cRes!=INF) cout<<cRes<<"\n";
        else cout<<"-1\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    Input();
    SetDp();
    Print();

    // cout<<"\n"; FOR(i,0,M){ FOR(j,0,M-1)  cout<<(mrg[i][j]==INF?"INF": to_string(mrg[i][j]))<<"\t"; cout<<"\n";}
}