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

#define ndl '\n'
#define ll long long
#define INF 1000000007
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()

using namespace std;


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n,k,m; cin>>n>>k>>m; 
    vector<vector<pair<ll,ll>>> cuksy(k+1, vector<pair<ll,ll>>());
    for(ll i=0;i<n;i++) {
        ll a,b,c; cin>>a>>b>>c;
        cuksy[a].push_back({b, c});
    }

    for(ll i=1;i<=k;i++) {
        if(cuksy[i].size() == 0) {
            cout<<0<<'\n';
            for(ll j=1;j<m;j++)
                cout<<-1<<'\n';
            return 0;
        }
    }

    vector<ll> mini_cena(m, -1), to_ale_ironicznie(m, -1);
    for(auto [b, c]: cuksy[1]) 
        if(to_ale_ironicznie[b%m] == -1 || to_ale_ironicznie[b%m] > c)
            to_ale_ironicznie[b%m] = c;
    
    for(ll ii = 2; ii<=k; ii++) {
        for(ll j = 0; j<m; j++) {
            mini_cena[j] = to_ale_ironicznie[j];
            to_ale_ironicznie[j] = -1LL;
        }
        for(auto [b, c]: cuksy[ii]) {
            for(ll j=0;j<m;j++) {
                if(mini_cena[j] == -1) continue;
                if(to_ale_ironicznie[(j + b)%m] == -1 || to_ale_ironicznie[(j + b)%m] > c + mini_cena[j]) {
                    to_ale_ironicznie[(j + b)%m] = c + mini_cena[j];
                } 
            }
        }
    }


    vector<pair<ll, ll>> mozliwosci;
    for(ll i=1; i<m; i++) {
        if(to_ale_ironicznie[i] != -1)
            mozliwosci.push_back({i, to_ale_ironicznie[i]});
    }
    // for(auto [a,b]:mozliwosci)
    //     cout<<a<<" "<<b<<"\n";


    vector<ll> dp(m, -1);
    dp[0] = 0;
    bool zm = 1;
    while(zm){
        zm = 0;
        for(ll i=0;i<m;i++)
            if(dp[i] != -1)
                for(auto [b, c]: mozliwosci)
                    if(dp[(b+i)%m] == -1 || dp[(b+i)%m] > c + dp[i]) {
                        zm = 1;
                        dp[(b+i)%m] = c + dp[i];
                    }
    }
        

    for(auto x:dp) cout<<x<<"\n";
}