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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll INF = 1e18;

struct item {
    ll m, c;
};

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

    ll n, K, M;
    cin >> n >> K >> M;

    vector<vector<item>> a(K);
    for (ll i = 0; i < n; i++) {
        ll k, m, c;
        cin >> k >> m >> c;
        k--;
        m %= M;
        a[k].push_back({m, c});
    }

    for (ll k = 0; k < K; k++) {
        if (a[k].empty()) {
            cout << "0\n";
            for (ll m = 1; m < M; m++)
                cout << "-1\n";
            return 0;
        }
    }

    vector<ll> b(M, INF);
    for (auto &item : a[0])
        b[item.m] = min(b[item.m], item.c);
    for (ll k = 1; k < K; k++) {
        vector<ll> tmp(M, INF);
        for (auto &item : a[k])
            for (ll m = 0; m < M; m++)
                tmp[(m + item.m) % M] = min(tmp[(m + item.m) % M], b[m] + item.c);
        swap(b, tmp);
    }

    vector<ll> ans(M, INF);
    ans[0] = 0;
    for (ll m = 1; m < M; m++) {
        ll gcd = __gcd(m, M);
        for (ll i = 0; i < gcd; i++) {
            ll j = i;
            do {
                ans[(j + m) % M] = min(ans[(j + m) % M], ans[j] + b[m]);
                j = (j + m) % M;
            } while (j != i);
            do {
                ans[(j + m) % M] = min(ans[(j + m) % M], ans[j] + b[m]);
                j = (j + m) % M;
            } while (j != i);
        }
    }
    for (ll m = 0; m < M; m++)
        if (ans[m] == INF)
            cout << "-1\n";
        else
            cout << ans[m] << "\n";

    return 0;
}