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
#include "bits/stdc++.h"
using namespace std;
#define all(x) x.begin(),x.end()
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << " " << p.second; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define ASSERT(...) 42
#endif
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
// const int oo = 1e9;
/*
DP[k][i] = remainder is i and you used k so far.
DP[k+1][i] = choose some multiset from them
can use exactly one of each colour.
Do DP for that?
DP[i][j] = min cost for choosing exactly one of each colour, and now at the j'th colour.
This is great, because it is quadratic.
So in the end have a DP array dp[i] = min cost to add +i.
Can be pretty arbitrary.
Can use any number of that DP array...
SO can just use them as distances? Great solved!
Could be the case that there is one very cheap element in them all.
cheap element can basically be 0.
0 is definitely best for 0.

all of those are distinct. when you look at all subsets
how many subsets can it avoid?

*/
const ll oo = 1e18;
void cmin(ll& a, ll b ) { a=min(a,b);}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k,m; cin >> n >> k >> m;
    vector<vector<pi>> js(k);
    for(int i=0;i<n;++i) {
        int col,w,c; cin >> col >> w >> c;
        js[col-1].push_back({w,c});
    }
    vector<ll> dp(m,oo);
    dp[0]=0;
    for(int i=0;i<k;++i) {
        vector<ll> ndp(m,oo);
        for(auto [w,c] : js[i]) {
            w%=m;
            for(int j=w;j<m;++j) {
                cmin(ndp[j],dp[j-w]+c);
            }
            for(int j=0;j<w;++j) {
                cmin(ndp[j],dp[j+m-w]+c);
            }
        }
        swap(dp,ndp);
    }
    vector<ll> dist(m,oo);
    dist[0]=0;
    vector<bool> vis(m);
    for(int i=0;i<m;++i) {
        int at=-1;
        for(int j=0;j<m;++j) if(!vis[j] and (at==-1 or dist[j]<dist[at])) at=j;
        vis[at]=1;
        if(dist[at]==oo) break;
        for(int to=0;to<m;++to) {
            cmin(dist[(at+to)%m],dist[at]+dp[to]);
        }
    }
    for(auto x : dist) {
        if(x==oo) cout << "-1\n";
        else cout << x << '\n';
    }
    
}