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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18;
const int MAXN = 7e3+7;
vector<pair<int,ll>> v[MAXN];
ll prev_dp[MAXN],dp[MAXN];
bool visited[MAXN];
vector<pair<int,ll>> war;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,k,m,a,b,ind,vis_cnt;	ll mini,c;
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		v[a].push_back({b,c});
	}
	for(int i=0;i<=m;i++) prev_dp[i]=dp[i]=INF;
	for(auto w:v[1]) prev_dp[w.first%m]=min(prev_dp[w.first%m],w.second);
	for(int i=2;i<=k;i++){
		for(auto w:v[i]) for(int j=0;j<m;j++) dp[(j+w.first)%m]=min(dp[(j+w.first)%m],prev_dp[j]+w.second);
		for(int j=0;j<m;j++){
			prev_dp[j]=dp[j];
			dp[j]=INF;
		}
	}
	for(int i=0;i<m;i++) dp[i]=prev_dp[i];
	for(int i=1;i<m;i++) if(dp[i]!=INF) war.push_back({i,dp[i]});
	while(vis_cnt<m){
		mini=INF; ind=0;
		for(int i=1;i<m;i++){
			if(visited[i]==1) continue;
			if(mini>dp[i]){
				mini=dp[i];
				ind=i;
			}
		}
		visited[ind]=1; vis_cnt++;
		for(auto w:war) dp[(ind+w.first)%m]=min(dp[(ind+w.first)%m],prev_dp[ind]+w.second);
		for(int i=0;i<m;i++) prev_dp[i]=dp[i];
	}
	cout<<0<<'\n';
	for(int i=1;i<m;i++) if(dp[i]==INF) cout<<-1<<'\n'; else cout<<dp[i]<<'\n';
	return 0;
}