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>
#include <queue>

using namespace std;

typedef long long lld;

int n, m, k;

struct gummy {
  lld weight, cost;
};

const int MAXC = 7000;
const lld INFTY = 4'000'000'000'000'000'000ll;

vector<gummy> colors[MAXC + 1];

vector<lld> calc_dp() {
  vector<lld> dp(m, -1);
  dp[0] = 0;

  for (int color = 1; color <= k; ++color) {
    vector<lld> next(m, -1);
    for (int rem = 0; rem < m; ++rem) {
      for (gummy x : colors[color]) {
        const int idx = (rem - x.weight + m) % m;
        if (dp[idx] < 0)
          continue;
        if (next[rem] < 0 || dp[idx] + x.cost < next[rem])
          next[rem] = dp[idx] + x.cost;
      }
    }
    dp = next;
  }
  return dp;
}

vector<lld> dijkstra(const vector<lld> &adj) {
  vector<vector<pair<lld, lld>>> v(m);
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < m; ++j) {
      if (adj[j] < 0)
        continue;
      v[i].push_back({adj[j], (i + j + m) % m});
    }
  }

  vector<lld> dist(m, -1);
  dist[0] = 0;
  priority_queue<pair<lld, lld>> q;
  q.push({0, 0});

  while (!q.empty()) {
    auto [d, x] = q.top();
    d = -d;
    q.pop();
    for (auto [l, u] : v[x]) {
      if (dist[u] == -1 || dist[u] > d + l) {
        dist[u] = d + l;
        q.push({-dist[u], u});
      }
    }
  }

  return dist;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k >> m;

  for (int i = 0; i < n; ++i) {
    int color, weight, cost;
    cin >> color >> weight >> cost;
    colors[color].push_back({weight, cost});
  }
  vector<lld> helper = calc_dp();

  vector<lld> res = dijkstra(helper);
  for (int i = 0; i < m; ++i)
    cout << res[i] << '\n';
}