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

using namespace std;

typedef long long ll;

const int MAXN = 7e3 + 7;
const ll INF = 1e18;

vector<pair<int, int>> zelki[MAXN];


void solve(){
	
	int n, k, m, ktory, weight, val;
	cin >> n >> k >> m;
	
	vector<ll> dp(m, INF);
	dp[0] = 0;
	
	for(int i = 1; i <= n; i++){
		
		cin >> ktory >> weight >> val;
		if(weight >= m) weight %= m;
		zelki[ktory].push_back({weight, val});
	}
	
	for(int j = 1; j <= k; j++){
		
		vector<ll> akt(m, INF);
		
		for(auto [weight, val] : zelki[j]){
			
			for(int i = 0; i < m; i++){
				
				if(dp[i] == INF) continue;				
				akt[(i + weight) % m] = min(dp[i] + val, akt[(i + weight) % m]);
			}
		}
		
		dp = akt;
	}
	
	dp[0] = 0;
	
	while(1){
		
		vector<ll> akt(m, INF), ost = dp;
		
		for(int i = 0; i < m; i++){
			
			if(dp[i] == INF) continue;
			
			for(int j = 0; j < m; j++){
				
				if(dp[j] == INF) continue;
				akt[(i + j) % m] = min(dp[i] + dp[j], akt[(i + j) % m]);
			}
		}
		
		for(int i = 0; i < m; i++){
			
			if(akt[i] < dp[i]) dp[i] = akt[i];
		}
		
		if(ost == dp) break;
	}	
	
	for(auto u : dp){
		
		if(u == INF) cout << "-1\n";
		else cout << u << '\n';
	}
}


signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int t = 1;
	//cin >> t;
	
	while(t--) solve();	
	
	return 0;
}