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

using namespace std;

const int N = 7000 + 2;
const long long INF = (long long)(1000 * 1000 * 1000 + 3) * (long long)(1000 * 1000 * 1000); 

vector<vector<long long>> zelki[N];

long long moves[N];
long long distances[N];
long long visited[N];

void prepare_moves(int m, int k) {
    vector<long long> dp(m, INF);
    dp[0] = 0;
    for (int i = k; i >= 1; i--) {
        vector<vector<long long>> next_dp(zelki[i].size());
        for (int j = 0; j < (int)zelki[i].size(); j++)
            next_dp[j].resize(m, INF);
        for (int j = 0; j < (int)zelki[i].size(); j++) {
            for (int l = 0; l < m; l++)
                next_dp[j][(l + zelki[i][j][0]) % m] = min(INF, dp[l] + zelki[i][j][1]);
        }
        for (int l = 0; l < m; l++) {
            dp[l] = next_dp[0][l]; //works beacue every color is present
            for (int j = 0; j < (int)next_dp.size(); j++)
                dp[l] = min(dp[l], next_dp[j][l]);
        }
    }
    for (int i = 0; i < N; i++)
        moves[i] = INF;
    for (int i = 0; i < m; i++)
        moves[i] = dp[i];
}

void dijkstra(int v, int m) {
    for (int i = 0; i < N; i++)
        distances[i] = INF;
    
    distances[v] = 0;
    priority_queue<pair<long long, long long>> next_vertex;
    next_vertex.push(make_pair(-distances[v], v));
    
    while (next_vertex.size() > 0) {
        int u = next_vertex.top().second;
        next_vertex.pop();
        if (visited[u])
            continue;
        visited[u] = 1;
        for (int i = 0; i < m; i++) {
            if (distances[u] + moves[i] < distances[(u + i) % m]) {
                distances[(u + i) % m] = distances[u] + moves[i];
                next_vertex.push(make_pair(-distances[(u + i) % m], (u + i) % m)); 
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    
    
    int n, k, m;
    int k_i, w_i, c_i;
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
        cin >> k_i >> w_i >> c_i;
        zelki[k_i].push_back({w_i, c_i});
    }
    for (int i = 1; i <= k; i++) {
        if (zelki[i].size() == 0) {
            cout << "0\n";
            for (int j = 1; j < m; j++)
                cout << "-1\n";
            return 0;
        }
    }
    prepare_moves(m, k);
    dijkstra(0, m); 
    for (int i = 0; i < m; i++)
        cout << ((distances[i] >= INF) ? -1 : distances[i]) << "\n";   
    return 0;
}