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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct zelek {
    int masa;
    long long cena;

    bool operator<(const zelek& other) const
    {
        return cena > other.cena;
    }
};

// zelki[k] - zelkis of color k
vector<zelek> zelki[7001];

// attainable values when taking one of each color
long long onelayer[2][7001];

bool cena_finalized[7001];
int total_unfinalized;
// vector<zelek> zelmalgamaty[2];

int main() {
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);
    for (int i = 0; i < n; ++i) {
        int zm, zk;
        long long zc;
        scanf("%d %d %lld", &zk, &zm, &zc);
        zelki[zk].push_back(zelek{zm, zc});
    }

    int curlayer = 0;
    for (int i = 1; i < m; ++i) {
        onelayer[0][i] = -1;
        onelayer[1][i] = -1;
    }
    onelayer[0][0] = -1;
    onelayer[1][0] = 0;

    // this is n*m cause thats total zelkis number
    for (int i = 1; i <= k; ++i) {
//        printf("ADDING COLOR %d\n", i);
//        printf("Onelayer status before color %d:\n", i);
//        for (int j = 0; j < m; ++j) {
//            printf("%2d: %lld\n", j, onelayer[1-curlayer][j]);
//        }
        if (zelki[i].empty()) {
            // Can't create any multisets save the empty one
            printf("0\n");
            for (int j = 1; j < m; ++j) {
                printf("-1\n");
            }
            return 0;
        }

        // prevlayer has no color i yet
        // curlayer may have 1 of color i already
        int prevlayer = 1 - curlayer;
        for (zelek &z: zelki[i]) {
            for (int j = 0; j < m; ++j) {
                if (onelayer[prevlayer][j] == -1) {
                    // gotta be more efficient here
                    continue;
                }
                int newmass = (j + z.masa) % m;
                long long newcost = onelayer[prevlayer][j] + z.cena;
                if (onelayer[curlayer][newmass] == -1 || onelayer[curlayer][newmass] > newcost) {
                    onelayer[curlayer][newmass] = newcost;
                }
            }
        }
        curlayer = 1 - curlayer;
        for (int j = 0; j < m; ++j) {
            onelayer[curlayer][j] = -1;
        }
//        printf("Onelayer status after color %d:\n", i);
//        for (int j = 0; j < m; ++j) {
//            printf("%2d: %lld\n", j, onelayer[1-curlayer][j]);
//        }
    }

    // onelayer[prevlayer] has now all attainable 1-each slices that must be used going forward
    // note: lowest value is already final

    long long bestscores[7001];
    for (int i = 1; i < m; ++i) {
        bestscores[i] = -1;
    }
    bestscores[0] = 0;
    cena_finalized[0] = true;
    total_unfinalized = m - 1;

    // int zelcurrent = 0;
    priority_queue<zelek> priq;

    for (int i = 1; i < m; ++i) {
        if (onelayer[1 - curlayer][i] != -1) {
            bestscores[i] = onelayer[1-curlayer][i];
            zelek bestsofar{i, bestscores[i]};
            priq.push(bestsofar);
//            printf("M: %d  | C: %lld\n", bestsofar.masa, bestsofar.cena);
        }
    }


    while(!priq.empty() && total_unfinalized != 0) {
        zelek x = priq.top();
        priq.pop();
        if (!cena_finalized[x.masa]) {
//            printf("Finalizing price for %d: %lld (%lld)\n", x.masa, bestscores[x.masa], x.cena);
            cena_finalized[x.masa] = true;
            total_unfinalized -= 1;
            for (int i = 1; i < m; ++i) {
                if (bestscores[i] == -1) {
                    continue;
                }
                int newmasa = (x.masa + i) % m;
                if (cena_finalized[newmasa]) continue;
                long long newcena = x.cena + bestscores[i];
                if (bestscores[newmasa] == -1 || bestscores[newmasa] > newcena) {
                    bestscores[newmasa] = newcena;
                    zelek newzelek{newmasa, newcena};
                    priq.push(newzelek);
                }
            }
        }
    }

    for (int i = 0; i < m; ++i) {
        printf("%lld\n", bestscores[i]);
    }

    return 0;
}