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
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<class T> T &ctmin(T &x){ return x; }
template<class T, class Head, class ...Tail> T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min<T>(x, h), t...); }
template<class T> T &ctmax(T &x){ return x; }
template<class T, class Head, class ...Tail> T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max<T>(x, h), t...); }



int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int nt, nc, nw;
	cin >> nt >> nc >> nw;
	vector<vector<int>> value(nc, vector<int>(nw, numeric_limits<int>::max()));
	for(auto i = 0; i < nt; ++ i){
		int c, w, v;
		cin >> c >> w >> v, -- c, w %= nw;
		ctmin(value[c][w], v);
	}
	vector<vector<int>> active_w(nc);
	for(auto c = 0; c < nc; ++ c){
		for(auto w = 0; w < nw; ++ w){
			if(value[c][w] != numeric_limits<int>::max()){
				active_w[c].push_back(w);
			}
		}
		if(active_w[c].empty()){
			cout << "0\n";
			for(auto w = 1; w < nw; ++ w){
				cout << "-1\n";
			}
			return 0;
		}
	}
	const long long inf = numeric_limits<long long>::max() / 4;
	vector<long long> dp(nw, inf);
	for(auto w: active_w[0]){
		ctmin(dp[w], value[0][w]);
	}
	auto reduce = [&](int wpref, int w)->int{
		return wpref + w >= nw ? wpref + w - nw : wpref + w;
	};
	for(auto c = 1; c < nc; ++ c){
		static vector<long long> dp_next(nw);
		ranges::fill(dp_next, inf);
		for(auto wpref = 0; wpref < nw; ++ wpref){
			if(dp[wpref] == inf){
				continue;
			}
			for(auto w: active_w[c]){
				ctmin(dp_next[reduce(wpref, w)], dp[wpref] + value[c][w]);
			}
		}
		swap(dp, dp_next);
	}
	vector<long long> res(nw, inf);
	res[0] = 0;
	for(auto w = 1; w < nw; ++ w){
		for(auto wpref = 0; wpref < nw; ++ wpref){
			ctmin(res[reduce(wpref, w)], res[wpref] + dp[w]);
		}
		for(auto wpref = 0; wpref < nw; ++ wpref){
			ctmin(res[reduce(wpref, w)], res[wpref] + dp[w]);
		}
	}
	for(auto x: res){
		if(x == inf){
			x = -1;
		}
		cout << x << "\n";
	}
	return 0;
}

/*

*/