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
// Author   : Jakub Rożek
// Task     : Żelki
// Contest  : PA 2024 r3 B
// Memory   : O(n^2)
// Time     : O(n^2)
// Solution : Rozwiązanie dobre

#include "bits/stdc++.h"
using namespace std;
using LL = long long;
template <typename T>
using P = pair<T, T>;
template <typename T>
using VV = vector<vector<T>>;
#define all(x) x.begin(), x.end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define ssize(x) int((x).size())
#ifdef DEBUG
template <typename T1, typename T2>
auto&operator<<(auto&o,pair<T1,T2>p){return o<<'('<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";for(auto e:x)o<<","<<e;return o<<"}";}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

const LL INF = 1'000'000'000'000'000'018;
// const LL N = 7'000;
const LL K = 7'000;
const LL M = 7'000;

LL n, k, m, x, y, z;
VV<P<LL>> towar; // towar[kolor][i] = <masa, cena>
LL zakup[K+1][M]; // ile zaplace za k kolorów o reszcze z masy m;
LL dp[M];
bool done[M];
vector<P<LL>> edge;

void solution() {
    cin >> n >> k >> m;
    towar.resize(k+1);
    REP (i, n) {
        cin >> x >> y >> z;
        y %= m;
        towar[x].push_back({y, z});
    }
    FOR (i, 1, k) {
        if (towar[i].empty()) {
            cout << "0\n";
            FOR (j, 1, m-1) {
                cout << "-1\n";
            }
            return;
        }
    }

    FOR (i, 0, k) {
        FOR (j, 0, m-1) {
            zakup[i][j] = INF;
        }
    }
    zakup[0][0] = 0;
    // n^2 bo k*m*(n/k)
    FOR (i, 1, k) {
        FOR (j, 0, m-1) {
            if (zakup[i-1][j] == INF) continue;
            for (auto p:towar[i]) {
                x = (j + p.first) % m;
                y = zakup[i-1][j] + p.second;
                zakup[i][x] = min(zakup[i][x], y);
            }
        }
    }

    REP (i, m) {
        dp[i] = zakup[k][i];
        done[i] = false;
        if (zakup[k][i] != INF) {
            edge.push_back({i, zakup[k][i]});
        }
    }

    dp[0] = 0;
    REP (d, m) {
        x = -1;
        y = INF;
        REP (i, m) {
            if (done[i]) continue;
            if (dp[i] <= y) {
                x = i;
                y = dp[i];
            }
        }
        for (auto i:edge) {
            y = (x + i.first) % m;
            z = dp[x] + i.second;
            dp[y] = min(dp[y], z);
        }
        done[x] = true;
    }

    REP (i, m) {
        if (dp[i] == INF) dp[i] = -1;
        cout << dp[i] << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tests = 1;
    // cin>>tests;
    FOR (i, 1, tests) {
        solution();
    }
    return 0;
}