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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#pragma GCC optimize("O3")
#endif

#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define endl '\n'
#define sp <<" "<<
#define eb emplace_back
#define MOD 1000000007
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

using ll = long long;
#define vec vector

template <class T> void print_v(vector<T> &v) { cout << "{"; for (auto x : v) cout << x << ","; cout << "}\n"; }
template <class T> void print_m(vector<vector<T>> &m) { for (auto v : m) print_v(v); cout << '\n'; }

#define fora(a) for(auto e:a)
#define it(i,s,e) for(long long int i=s;i<e;i++)
#define ita(i,s,e) for(long long int i=s;i<=e;i++)
#define itr(i,e,s) for(long long int i=e-1;i>=s;i--)
#define urs(r...)typename decay<decltype(r)>::type
#define rep(i,n)for(urs(n)i=0;i<(n);++i)


const long NOT_REACHABLE = LONG_MAX;
const int MAX = 7000 + 10;
// color -> (weight, cost)
vec<vec<pair<long,long>>> jellies(MAX);
long colors, mod;

long combos[MAX];

void gen_1_jelly_combos() {
    long prev[MAX];
    fill(std::begin(prev), std::begin(prev)+mod, NOT_REACHABLE);
    prev[0] = 0;
    long next[MAX];

    for (int c=1; c<= colors; c++) {
        if (!jellies[c].size()) {
            for (int i=0; i<mod; i++) {
                combos[i] = NOT_REACHABLE;
            }
        }
        fill(std::begin(next), std::begin(next)+mod, NOT_REACHABLE);

        for (auto [m, c]: jellies[c]) {
            for (int i=0; i<mod; i++) {
                if (prev[i] != NOT_REACHABLE) {
                    next[(i+m) % mod] = min(next[(i+m) % mod], prev[i]+c);
                }
            }
        }

        for (int i=0; i<mod; i++) {
            prev[i] = next[i];
        }
    }

    for (int i=0; i<mod; i++) {
        combos[i] = prev[i];
    }
}

void solve() {
    gen_1_jelly_combos();
    //print_v(combos);

    vec<bool> visited(mod);
    
    for (int offset=1; offset<mod; offset++) {
        long val = combos[offset];
        if (val == NOT_REACHABLE) continue;
        
        for (int pos=0; pos<mod; pos++) {
            int p = pos;
            if (combos[p] == NOT_REACHABLE) continue;

            for (int i=0; i<2*mod+10; i++) {
                int next = (p+offset)%mod;
                
                if (combos[p] + val < combos[next]) {
                    combos[next] = combos[p] + val;
                    p = next;
                } else {
                    break;
                }
            }

        }
    }

    combos[0] = 0;

    for (int i=0; i<mod; i++) {
        long val = combos[i];
        if (val == NOT_REACHABLE) val = -1;
        cout << val << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long n;
    cin >> n >> colors >> mod;

    rep (_, n) {
        int k, m, c;
        cin >> k >> m >> c;
        jellies[k].eb(m,c);
    }
    

    solve();

    return 0;
}