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

#define loop(i, a, b) for(ll i = a; i <= b; i++)
#define loop_rev(i, a, b) for(ll i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) ll(x.size())
#define eb emplace_back
#define pb push_back

using ll = int64_t;

constexpr ll MAX_N = 7'000 + 1;
constexpr ll MAX_K = 7'000 + 1;
constexpr ll MAX_M = 7'000 + 1;

struct Jelly { short weight; ll cost; };

ll dp[MAX_M], temp_dp[MAX_M], final_res[MAX_M];
vector<Jelly> jellies_of_color[MAX_K];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  ll n, k, m; cin >> n >> k >> m;

  loop(i, 0, n-1) {
    short color, weight; ll cost;
    cin >> color >> weight >> cost;
    jellies_of_color[color].emplace_back(weight % m, cost);
  }

  constexpr ll UNDEF = 1e18;
  fill(dp, dp + m, UNDEF);
  fill(final_res, final_res + m, UNDEF);
  fill(temp_dp, temp_dp + m, UNDEF);

  dp[0] = 0;

  loop(col, 1, k) {
    loop(r, 0, m-1) {
      for(auto const& jelly : jellies_of_color[col]) {
        if(dp[r] == UNDEF) continue;
        ll j = (r + jelly.weight); if(j >= m) j -= m;
        if(dp[r] + jelly.cost < temp_dp[j]) {
          temp_dp[j] = dp[r] + jelly.cost;
        }
      }
      dp[r] = UNDEF;
    }
    swap(dp, temp_dp);
  }

  dp[0] = 0;

  loop(i, 0, m-1) {
    ll min_val = UNDEF; ll ind = 0;
    loop(r, 0, m-1) {
      if(final_res[r] != UNDEF) continue;
      if(dp[r] < min_val) {
        min_val = dp[r];
        ind = r;
      }
    }
    final_res[ind] = dp[ind];
    loop(r, 0, m-1) {
      ll new_r = (ind + r); if(new_r >= m) new_r -= m;
      temp_dp[new_r] = min(dp[new_r], dp[r] + dp[ind]);
    }
    swap(temp_dp, dp);
  }

  loop(i, 0, m-1) {
    if(final_res[i] == UNDEF) cout << "-1\n";
    else cout << final_res[i] << '\n';
  }

}