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
#include <bits/stdc++.h>
using namespace std;

template <typename T> void set_min(T& a, const T& b){
	if(b < a) a = b;
}
template <typename T> void set_max(T& a, const T& b){
	if(b > a) a = b;
}

using ll = int64_t;

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, K, M;
	cin >> N >> K >> M;
	vector<vector<pair<int, ll> > > costs_by_color(K);
	for(int i = 0; i < N; i++){
		int k, m;
		ll C;
		cin >> k >> m >> C;
		k--;
		m %= M;
		costs_by_color[k].push_back({m, C});
	}
	ll INF = 1e18;
	vector<ll> one_each(M, INF);
	one_each[0] = 0;
	for(int k = 0; k < K; k++){
		vector<ll> new_one_each(M, INF);
		for(auto [m, C] : costs_by_color[k]){
			for(int i = 0; i < M; i++){
				set_min(new_one_each[(i+m)%M], one_each[i] + C);
			}
		}
		one_each = new_one_each;
	}
	vector<ll> dp(M, INF);
	dp[0] = 0;
	using pq_t = pair<ll, int>;
	priority_queue<pq_t, vector<pq_t>, greater<pq_t>> pq;
	pq.push({dp[0], 0});
	while(!pq.empty()){
		auto [cost, v] = pq.top();
		pq.pop();
		if(dp[v] != cost) continue;
		for(int m = 0; m < M; m++){
			ll ncost = cost + one_each[m];
			int nv = (m + v) % M;
			if(ncost < dp[nv]){
				dp[nv] = ncost;
				pq.push({dp[nv], nv});
			}
		}
	}
	for(int i = 0; i < M; i++){
		if(dp[i] >= INF){
			cout << -1 << '\n';
		} else {
			cout << dp[i] << '\n';
		}
	}
}