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

#define int long long

using namespace std;

void solve() {
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<array<int, 2>>> cols(k);
    for (int i = 0; i < n; i++) {
        int col, mass, price;
        cin >> col >> mass >> price;
        cols[--col].push_back({mass, price});
    }
    vector<int> res1(m, 1ll<<60), res2(m, 1ll<<60);
    res1[0] = 0;
    for (int col = 0; col < k; col++) {
        fill(res2.begin(), res2.end(), 1ll<<60);
        // for (int v : res1) cerr << v << " "; cerr << endl;
        for (auto &p : cols[col]) {
            int mass = p[0];
            int price = p[1];
            // cerr << col << " " << mass << " " << price << endl;
            for (int r = 0; r < m; r++) {
                int ix = r + mass;
                if (ix >= m) ix -= m;
                res2[ix] = min(res2[ix], res1[r] + price);
            }
        }
        swap(res1, res2);
    }
    
    // vector<int> d(m, 1ll<<60);
    // vector<bool> vis(m, false);
    // d[0] = 0;
    // for (int i = 0; i < m; i++) {
    //     int v = -1;
    //     for (int j = 0; j < m; j++) {
    //         if (!vis[j] && (v < 0 || d[j] < d[v])) v = j;
    //     }
    //     if (d[v] >= 1ll<<60) break;
    //     vis[v] = true;
    //     for (int r = 1; r < m; r++) {
    //         int ix = v + r;
    //         if (ix >= m) ix -= m;
    //         if (d[v] + res1[r] < d[ix]) {
    //             d[ix] = d[v] + res1[r];
    //         }
    //     }
    // }
    // d[0] = 0;
    // for (int v : d) {
    //     cout << ((v >= (1ll<<60)) ? -1 : v) << '\n';
    // }

    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < m; i++) {
            for (int j = i; j < m; j++) {
                int ix = i + j;
                if (ix >= m) ix -= m;
                int cand = res1[i] + res1[j];
                if (cand < res1[ix]) {
                    res1[ix] = cand;
                    changed = true;
                }
            }
        }
    }
    res1[0] = 0;
    for (int v : res1) {
        cout << ((v >= (1ll<<60)) ? -1 : v) << '\n';
    }
}

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

// #ifdef LOCAL
//     int t; cin >> t; while (t--)
// #endif

    solve();

    cout.flush();
}