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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// Daniel Grzegorzewski
// while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(SEED);

const int N = 7003;
const int INF = (int)1e17;

int n, k, m, mn[2][N], res[2][N];
int col[N], si[N], pr[N];
VI ind[N];

signed main() {
  init_ios();
  cin >> n >> k >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> col[i] >> si[i] >> pr[i];
    if (si[i] == m)
      si[i] = 0;
    ind[col[i]].PB(i);
  }
  for (int i = 1; i <= k; ++i)
    if (ind[i].size() == 0) {
      cout<<"0\n";
      for (int j = 1; j < m; ++j)
        cout<<"-1\n";
      return 0;
    }
  for (int i = 1; i < m; ++i)
    mn[0][i] = INF;
  for (int i = 1; i <= k; ++i) {
    for (int j = 0; j < m; ++j)
      mn[1][j] = INF;
    for (auto id: ind[i]) {
      for (int masa = 0; masa < m; ++masa) {
        int prv = masa-si[id];
        if (prv < 0)
          prv += m;
        mn[1][masa] = min(mn[1][masa], mn[0][prv]+pr[id]);
      }
    }
    for (int j = 0; j < m; ++j)
      mn[0][j] = mn[1][j];
  }
  for (int j = 1; j < m; ++j) {
    int cur = j;
    if (mn[0][j] >= INF)
      continue;
    for (int k = 2; k < m; ++k) {
      cur += j;
      if (cur >= m)
        cur -= m;
      if (cur == j)
        break;
      if (k*mn[0][j] > INF)
        break;
      mn[0][cur] = min(mn[0][cur], k*mn[0][j]);
    }
  }
  for (int i = 1; i < m; ++i)
    res[0][i] = INF;
  for (int i = 1; i < m; ++i) {
    if (mn[0][i] >= INF)
      continue;
    for (int j = 0; j < m; ++j)
      res[1][j] = res[0][j];
    for (int masa = 0; masa < m; ++masa) {
      int prv = masa-i;
      if (prv < 0)
        prv += m;
      res[1][masa] = min(res[1][masa], res[1][prv]+mn[0][i]);
    }
    for (int j = 0; j < m; ++j)
      res[0][j] = res[1][j];
  }
  for (int i = 0; i < m; ++i) {
    if (res[0][i] >= INF)
      res[0][i] = -1;
    cout<<res[0][i]<<"\n";
  }
}