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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio();
    int N, K, M;
    cin >> N >> K >> M;
    vector<vector<pair<int, int>>> Z(K);

    for (int i = 0; i < N; ++i) {
        int k, m, c;
        cin >> k >> m >> c;
        Z[k - 1].push_back({m, c});
    }

    vector<long long> A(M, -1);
    A[0] = 0;

    if (any_of(Z.begin(), Z.end(), [](const vector<pair<int, int>>& z) { return z.empty(); })) {
        for (int i = 0; i < M; ++i)
            cout << A[i] << endl;
    } else {
        vector<long long> D(M, -1);
        D[0]=0;
        int constans = 1;
        int ile=0;
        while (constans < 2) {
            constans++;
            ile++;
            for (int k = 0; k < K; ++k) {
                vector<long long> E(M, -1);
                for (auto z : Z[k]) {
                    for (int m = 0; m < M; ++m) {
                        if (D[m] >= 0) {
                            int w = (m + z.first) % M;
                            long long cost = D[m] + z.second;
                            if (E[w] < 0 || cost < E[w]) {
                                E[w] = cost;
                            }
                        }
                    }
                }
                D = E;
            }
            for (int m = 0; m<M; ++m) {
                if (D[m]>=0) {
                    long long cost = D[m];
                    int i=(2*m)%M,k=2;
                    while (i != m) {
                        //cout << i << ", ";
                        if (D[i]==-1 || cost*k<D[i])
                            D[i]=cost*k;
                        k++;
                        i=(i+m)%M;
                    }
                break;
                }
            }
            //cout << "-------------\n";
            for (int m = 0; m < M; ++m) {
                if (D[m] >= 0 && (A[m] == -1 || D[m] < A[m])) {
                    A[m] = D[m];
                    //cout << ile << ":" << m << " " << A[m] << endl;
                    constans = 0;
                }
            }
        }

        for (int i = 0; i < M; ++i) {
            cout << A[i] << endl;
        }
    }

    return 0;
}