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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using db = long double;

using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define per(i,a,b) for(int i = (b) - 1; i >= (a); i--)

#ifdef LOCAL
template<class A, class B> auto& operator<<(auto &o, pair<A, B> p) { return o << '(' << p.x << ", " << p.y << ')'; }
template<class... A> auto& operator<<(auto &o, tuple<A...> t) {
	bool is_first = true;
	o << "(";
	apply([&o, &is_first](auto... a) {((o << (is_first ? (is_first = false, "") : ", ") << a), ...);}, t);
	o << ")";
	return o;
}
auto& operator<<(auto& o, auto a) {
	bool is_first = true;
	o << "{";
	for (auto b : a) o << (is_first ? (is_first = false, "") : ", ") << b;
	return o << "}";
}
void dump(auto... x) {
	bool is_first = true;
	((cerr << (is_first ? (is_first = false, "") : ", ") << x), ...) << "\n";
}
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) ;
#endif

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

constexpr int N = 7007;
constexpr ll INF = 1e18 + 213742069;

vpi types[N];
ll dp[2][N];
ll res[N];

// mt19937 gen(2137);
// int rand_int(int l, int r) {
// 	 return uniform_int_distribution<int>{l, r}(gen);
// }

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	// int n = 7000, k = rand_int(100, 200), m = 7000;
	int n, k, m;
	cin >> n >> k >> m;
	rep(i, 1, n + 1) {
		// int color = rand_int(1, k), mass = rand_int(1, m), price = rand_int(1, 1e9);
		int color, mass, price;
		cin >> color >> mass >> price;
		if (mass == m) mass = 0;
		types[color].eb(mass, price);
	}
	
	rep(mass, 0, m) dp[0][mass] = dp[1][mass] = INF;
	dp[0][0] = 0;
	rep(color, 1, k + 1) {
		rep(mass, 0, m)  dp[color & 1][mass] = INF;
		for (const auto &[mass, price] : types[color]) {
			int new_mass = mass;
			rep(old_mass, 0, m) {
				ckmin(dp[color & 1][new_mass], dp[(color & 1) ^ 1][old_mass] + price);
				if (++new_mass == m) new_mass = 0;
			}
		}
	}
	
	rep(mass, 0, m) res[mass] = INF;
	res[0] = 0;
	
	rep(mass, 0, m) {
		if (dp[k & 1][mass] < INF) {
			const ll price = dp[k & 1][mass];
			const int gcd = __gcd(mass, m);
			rep(i, 0, gcd) {
				pair<ll, int> start(res[i], i);
				int j = i, nxt = i + mass;
				if (nxt >= m) nxt -= m;
				do {
					ckmin(start, mp(res[j], j));
					j = nxt;
					nxt += mass;
					if (nxt >= m) nxt -= m;
				} while (j != i);
				
				j = start.y, nxt = start.y + mass;
				if (nxt >= m) nxt -= m;
				do {
					ckmin(res[nxt], res[j] + price);
					j = nxt;
					nxt += mass;
					if (nxt >= m) nxt -= m;
				} while (j != start.y);
			}
		}
	}
	
	rep(mass, 0, m) {
		if (res[mass] == INF) res[mass] = -1;
		cout << res[mass] << "\n";
	}
	
	return 0;
}