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
// Jan Zakrzewski
#include <bits/stdc++.h>
using namespace std;

struct Zelek {
    int kolor;
    int masa;
    int cena;
};

int constexpr Z = 7010;
int N, K, M;
vector<Zelek> wedlug_kolorow[Z];

long long constexpr INF = 1e18;
long long dp[Z];
long long dp_oth[Z];
bool vis[Z];

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

    cin >> N >> K >> M;
    for(int k = 1; k <= K; ++k) wedlug_kolorow[k].clear();
    for(int i = 1; i <= N; ++i) {
        Zelek zelek;
        cin >> zelek.kolor;
        cin >> zelek.masa;
        cin >> zelek.cena;
        wedlug_kolorow[zelek.kolor].push_back(zelek);
    }

    dp[0] = 0;
    for(int x = 1; x <= M-1; ++x) dp[x] = INF;

    for(int k = 1; k <= K; ++k) {
        for(int x = 0; x <= M-1; ++x) dp_oth[x] = INF;
        for(Zelek zelek : wedlug_kolorow[k]) {
            for(int x = 0; x <= M-1; ++x) {
                int y = (x + zelek.masa) % M;
                dp_oth[y] = min(dp_oth[y], dp[x] + zelek.cena);
            }
        }
        for(int x = 0; x <= M-1; ++x) dp[x] = dp_oth[x];
    }

    for(int x = 0; x <= M-1; ++x) vis[x] = false;
    dp[0] = 0;
    vis[0] = true;
    while(true) {
        int m;
        long long c = INF;
        for(int x = 0; x <= M-1; ++x) {
            if(vis[x]) continue;
            if(dp[x] < c) {
                m = x;
                c = dp[x];
            }
        }
        if(c == INF) break;
        vis[m] = true;

        for(int x = 0; x <= M-1; ++x) {
            int y = (x + m) % M;
            dp[y] = min(dp[y], dp[x] + c);
        }
    }


    for(int x = 0; x <= M-1; ++x) {
        if(dp[x] < INF) cout << dp[x] << "\n";
        else cout << "-1\n";
    }

    return 0;
}