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
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
struct Node {
  int m;
  long c;
  Node(int m = 0, long c = 0) : m(m), c(c) {
  }
};
template < typename T >
int mod(T v, T m) {
  return (v < m) ? v : ((v -= m) < m) ? v
                                      : (v % m);
}
struct Solution {
  vector< long > v;
  Solution(int m, vector< Node > const &vn) : v(m, LONG_MAX) {
    vector< int > ready;
    ready.reserve(m);
    for (vector< Node >::const_iterator it = vn.begin(); it != vn.end(); ++it) {
      Node const &base = *it;
      if (v[base.m] == LONG_MAX)
        ready.push_back(base.m);
      v[base.m] = min(v[base.m], base.c);
      vector< int > extras;
      int ready_size = ready.size();
      for (int i = 0; i < ready_size + (int)extras.size(); ++i) {
        int a = i < ready_size ? ready[i] : extras[i - ready_size];
        int j = mod(a + base.m, m);
        long r = min(v[j], v[a] + v[base.m]);
        if (v[j] == LONG_MAX)
          ready.push_back(j);
        if (v[j] > r)
          extras.push_back(j);
        v[j] = r;
      }
    }
    v[0] = 0;
  }
  long operator[](int i) const {
    return v[i] == LONG_MAX ? -1 : v[i];
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k, m, a, b, c;
  cin >> n >> k >> m;
  vector< vector< Node > > colors(k);
  while (n-- && cin >> a >> b >> c)
    colors[--a].push_back(Node(mod(b, m), c));
  vector< Node > data[2];
  int id = 0;
  data[id].push_back(Node(0, 0));
  vector< int > pos(m);
  vector< int > check(m, 0);
  int marker = 0;
  while (k--) {
    vector< Node > &col = colors[k];
    vector< Node > &src = data[id], &dst = data[id ^= 1];
    ++marker;
    for (vector< Node >::const_iterator it = src.begin(); it != src.end(); ++it)
      for (vector< Node >::iterator node = col.begin(); node != col.end(); ++node) {
        long p = mod((*it).m + (*node).m, m);
        if (check[p] != marker) {
          check[p] = marker;
          pos[p] = dst.size();
          dst.push_back(Node(p, (*it).c + (*node).c));
        } else
          dst[pos[p]].c = min(dst[pos[p]].c, (*it).c + (*node).c);
      }
    src.clear();
  }
  Solution s(m, data[id]);
  for (int i = 0; i < m; ++i)
    cout << s[i] << '\n';
}