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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 7e3+10;
const ll INF = 1e18+10;

ll dp[N][N], n, k, m, dist[N];
vector<pii> v[N];

void solve() {
    cin>>n>>k>>m;

    for (int i=1; i<=n; ++i) {
        int ki, mi, ci; cin>>ki>>mi>>ci; mi%=m;
        v[ki].push_back({mi, ci});
    }

    for (int i=0; i<N; ++i) {
        for (int j=0; j<N; ++j) dp[i][j]=INF;
    } dp[0][0]=0;

    for (int i=1; i<=k; ++i) {
        for (auto u : v[i]) {
            for (int j=0; j<m; ++j) {
                dp[i][(j+u.first)%m]=min(dp[i][(j+u.first)%m], dp[i-1][j]+u.second);
            }
        }
    }

    for (int i=0; i<m; ++i) dist[i]=INF;
    dist[0]=0;

    bool vis[m+10]={};
    for (int i=0; i<m; ++i) {
        int v=-1;
        for (int j=0; j<m; ++j) {
            if (!vis[j] && (v == -1 || dist[j] < dist[v])) v=j;
        }

        if (dist[v] == INF) break;

        vis[v]=true;
        for (int j=0; j<m; ++j) {
            int u=(v+j)%m;
            if (dist[u] > dist[v]+dp[k][j]) {
                dist[u]=dist[v]+dp[k][j];
            }
        }
    }

    for (int i=0; i<m; ++i) {
        if (dist[i] >= INF) cout<<"-1\n";
        else cout<<dist[i]<<"\n";
    }
}

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

    int t=1; //cin>>t;
    while (t--) solve();
}