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

using namespace std;

typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define rep(i,b,e) for(int i=(b); i<(e); i++)
#define each(a,x)  for(auto &a : (x))
#define all(x) (x).begin(), (x).end()
#define sz(x)  (int)(x).size()

template <class T, class U> auto &operator<<(ostream &out, pair<T, U> a) { return out << "(" << a.first << ", " << a.second << ")"; }
template <class T, class = class enable_if<!is_same<T, string>(), class T::iterator>::type> auto &operator<<(ostream &out, T a) {
    out << "{";
    bool fi = 1;
    for(auto b : a) {
        if(fi) {out<<b; fi=0;}
        else out<<", "<<b;
    }
    return out << "}";
}
void dump(){
   cerr << "\e"<<"\n";
}
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
// #define debug(...) cerr << "\e"<<__func__<<":"<<__LINE__<<"\t"<<"[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#define debug(...) ;

const int N = 7050;
const ll INF = 1e18;
vector<pii> misie[N];
ll minKoszt[N],Prev[N],dp[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k,m;
    cin >> n >> k >> m;
    rep(i,0,n){
        int kolor,masa,koszt;
        cin >> kolor >> masa >> koszt;
        misie[kolor].pb({masa%m,koszt});
    }
    rep(i,0,m+5){
        minKoszt[i] = INF;
        dp[i] = INF;
    }
    minKoszt[0] = 0;
    rep(kolor,1,k+1){   
        rep(i,0,m){
            Prev[i] = minKoszt[i];
            minKoszt[i] = INF;
        } 
        each(mis,misie[kolor]){
            auto &[masa,koszt] = mis;
            rep(waga,0,m)
                // if(Prev[(waga-masa+m)%m]<INF)
                    minKoszt[waga] = min({minKoszt[waga],minKoszt[waga], Prev[(waga-masa+m)%m]+koszt});
        }
    }      
    dp[0] = 0;
    queue<pair<ll,int>> toAnalyze;
    toAnalyze.push({0,0});
    int smallest[m];
    for(int i=0; i<m; ++i) smallest[i] = i;
    sort(smallest,smallest+m,[](const int &a, const int &b){
        return minKoszt[a]<minKoszt[b];
    });
    ll dist,x;
    int V,Next;
    while(!toAnalyze.empty()){
        dist = -toAnalyze.front().first;
        x = toAnalyze.front().second;
        toAnalyze.pop();
        if(dp[x]!=dist)
            continue;
        for(int i=0; i<m; ++i){
            V = smallest[i];
            if(minKoszt[V]>=INF) break;
            Next = (x+V) - (x+V>=m)*m;
            if(dp[x]+minKoszt[V] < dp[Next]){
                dp[Next] = dp[x]+minKoszt[V];
                toAnalyze.push({-dp[Next],Next});
            }
            // dp[Next] = min(dp[Next], dp[x]+minKoszt[V]);
        }
    }  
    rep(i,0,m)
        cout << (dp[i]<INF ? dp[i] : -1) << "\n";
    return 0;
}