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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define ft first
#define sc second
#define pb push_back
#define FOR(i,n) for(int i=0; i<n; i++)
#define FORX(i,a,b) for(int i=(a); i<=(b); i++)
#define watch(x) cerr << (#x) << " == " << (x) << endl
typedef long long ll;
typedef long double ld;
using namespace std;

ll m;
ll pack[7007], new_pack[7007];
ll dp[7007], new_dp[7007];
bool vis[7007];

vector<pair<ll,ll>> candy[7007];

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

ll n,k;
cin>>n>>k>>m;

FOR(i,n){
    int col, mass, cost;
    cin>>col>>mass>>cost;
    candy[col].pb({mass%m,cost});
}

FORX(i,1,k){
    if (candy[i].empty()) {
        cout<<0<<"\n";
        FORX(j,1,m-1){
            cout<<-1<<"\n";
        }
        return 0;
    }
}

fill(pack, pack+m+5, INT_MAX);
fill(new_pack, new_pack+m+5, INT_MAX);
pack[0] = 0;

FORX(i,1,k) {
    FOR(j,m){
        if (pack[j] == INT_MAX) continue;
        for (auto &p : candy[i]) {
            new_pack[(j+p.ft)%m] = min(new_pack[(j+p.ft)%m], pack[j]+p.sc);
        }
    }
    FOR(j,m){
        pack[j] = new_pack[j];
        new_pack[j] = INT_MAX;
    }
}
pack[0] = 0;

fill(dp, dp+m+5, INT_MAX);
fill(new_dp, new_dp+m+5, INT_MAX);
dp[0] = 0;


FOR(i,m){
    pair<int,int> low = {INT_MAX, INT_MAX};
    FOR(j,m){
        if (!vis[j]) {
            low = min(low, {dp[j], j}); 
        }
    }
    int pos = low.sc;
    int cost = low.ft;
    vis[pos] = 1;
    if (cost == INT_MAX) {break;}
    FORX(j,1,m-1) {
        if (pack[j] == INT_MAX) {continue;} 
        dp[(pos+j)%m] = min(dp[(pos+j)%m], cost+pack[j]);
    }
}


FOR(i,m){
    cout<<(dp[i] == INT_MAX ? -1 : dp[i])<<"\n";
}

return 0;
}