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
// 2024 HOPE IN VALUABLE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=7005;
const ll inff=1ll<<60;
int n,K,m,vis[N]; vector<pair<int,int> >vec[N]; ll f[N],g[N],ans[N];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>K>>m;
	for(int i=1;i<=n;i++){
		int k,w,c; cin>>k>>w>>c;
		vec[k].emplace_back(w,c);
	}
	for(int i=1;i<m;i++) f[i]=inff;
	for(int i=1;i<=K;i++){
		for(int j=0;j<m;j++) g[j]=f[j],f[j]=inff;
		for(pair<int,int> k:vec[i]){
			int x=k.first%m,y=k.second;
			for(int j=0,w=x;j<m;j++,w=(w==m-1?0:w+1)) if(g[j]!=inff) f[w]=min(f[w],g[j]+y);
		}
	}
	for(int i=1;i<m;i++) ans[i]=inff; 
	while(1){
		int p=-1;
		for(int i=0;i<m;i++) if(!vis[i]&&(p==-1||ans[i]<ans[p])) p=i;
		if(p==-1) break; vis[p]=1;
		for(int i=0,q=p;i<m;i++,q=(q==m-1?0:q+1)) ans[q]=min(ans[q],ans[p]+f[i]);
	}
	for(int i=0;i<m;i++) if(ans[i]==inff) ans[i]=-1;
	for(int i=0;i<m;i++) cout<<ans[i]<<'\n';
	return 0;
}