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
#include <iostream>
#include <vector>
using namespace std;
long long inf=1000000000000000003;
struct s1{
	long long m,c;
};
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	long long n,k,m;
	cin >> n >> k >> m;
	vector<vector<s1>>v(k+1);
	for(long long i=0;i<n;i++){
		long long a,b,c;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
	}
	vector<long long>dpo(m,0),dpn(m,inf),cinf(m,inf);
	dpn[0]=0;
	for(auto&i:v){//i to vector s1
		for(auto&j:i){//j to s1
			for(long long z=0;z<m;z++){
				long long nx=z+j.m; 
				nx%=m;
				dpn[nx]=min(dpn[nx],dpo[z]+j.c);
			}
		}
		dpo=dpn;
		dpn=cinf;
	}
	//w dpn wynik 
	/*for(auto&i:dpn){cout<<i<<" ";}
	cout<<endl;*/
	dpn=dpo;
	vector<long long>razy(m,inf);
	razy[0]=0;
	for(long long i=1;i<m;i++){
		for(long long j=1;j<m;j++){
			long long nx=i*j;
			nx%=m;
			razy[nx]=min(razy[nx],dpn[i]*j);
		}
	}
	vector<long long>o(m,inf);
	o[0]=0;
	for(long long i=0;i<m;i++){
		if(o[i]==inf){continue;}
		for(long long j=1;j<m;j++){
			long long nx=i+j;
			nx%=m;
			o[nx]=min(o[nx],o[i]+razy[j]);
		}
	}
	for(auto&i:o){
		if(i==inf){i=-1;}
		cout<<i<<endl;
	}
}