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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#define st first
#define nd second
typedef long long ll;
using namespace std;

struct zelek {
    ll color;
    ll mass;
    ll cost;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, m; cin >> n >> k >> m;
    vector<zelek> zelki(n);
    for (int i = 0; i < n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        zelki[i] = {a, b, c};
    }
    for (int i = 1; i <= k; i++) {
        zelek e = {i, 0, (ll)1e18};
        zelki.push_back(e);
    }
    sort(zelki.begin(), zelki.end(), [](zelek a, zelek b){
        if (a.color != b.color) return a.color < b.color;
        if (a.mass != b.mass) return a.mass < b.mass;
        return a.cost < b.cost;
    });
    vector<ll> edges(m, 1e18), e2(m, 1e18);
    edges[0] = 0;
    int curcol = 1;
    for (auto z: zelki) {
        if (z.color != curcol) {
            edges = e2;
            e2 = vector<ll>(m, 1e18);
            curcol++;
            // if (curcol != z.color) break;
        }
        for (int i = 0; i < m; i++) {
            e2[(i+z.mass)%m] = min(e2[(i+z.mass)%m], edges[i]+z.cost);
        }
    }
    edges = e2;
    vector<ll> d(m, 1e18);
    d[0] = 0;
    set<pair<ll, int>> s;
    s.insert({0, 0});
    while (!s.empty()) {
        int u = (*s.begin()).nd;
        s.erase(s.begin());
        for (int i = 1; i < m; i++) {
            int v = (u+i)%m;
            if (d[v] > d[u] + edges[i]) {
                s.erase({d[v],v});
                d[v] = d[u] + edges[i];
                s.insert({d[v],v});
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if (d[i] == 1e18) cout << "-1\n";
        else cout << d[i] << '\n';
    }
    // for (int i = 0; i < m; i++) cout << edges[i] << '\n';

}