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
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>>el;
vector<long long>zel[7001];
long long uz[7001][7001],off[7001],wyn[7001];
priority_queue<pair<long long,int>>pq;
const long long mask=(1ll<<30)-1;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,k,m,a,b,s;
	long long w,v;
	cin>>n>>k>>m;
	for(int i=0;i<=k;++i){
		for(int j=0;j<=m;++j)uz[i][j]=1ll<<60;//i-ile kolorów j-jakie modulo
	}
	for(int i=0;i<m;++i){
		wyn[i]=1ll<<60;
		off[i]=1ll<<60;
	}
	for(int i=0;i<n;++i){
		cin>>a>>b>>w;
		zel[a].emplace_back(((long long)b<<30)+w);
	}
	uz[0][0]=0;
	for(int i=0;i<=k;++i){
		for(int j=0;j<m;++j){
			if(uz[i][j]<(1ll<<60)){
				for(int h=0;h<(int)zel[i+1].size();++h){
					a=(int)(zel[i+1][h]>>30);w=zel[i+1][h]&mask;
					s=j+a;
					if(s>=m)s-=m;
					if(uz[i][j]+w<uz[i+1][s])uz[i+1][s]=uz[i][j]+w;
				}	
			}
		}
	}
	for(int i=0;i<m;++i)if(uz[k][i]<(1ll<<60))el.emplace_back(i,uz[k][i]);
	wyn[0]=0;off[0]=0;
	for(int i=0;i<(int)el.size();++i){
		a=el[i].first;v=el[i].second;
		for(long long j=1;j<m;++j){
			w=j*a%m;
			if(off[w]>v*j)off[w]=v*j;
		}
	}
	for(int i=1;i<m;++i){
		for(int j=0;j<m;++j){
			a=(j+i)%m;
			wyn[a]=min(wyn[a],wyn[j]+off[i]);
		}
	}
	for(int i=0;i<m;++i){
		if(wyn[i]<(1ll<<60))cout<<wyn[i]<<"\n";
		else cout<<-1<<"\n";
	}
	//cout<<"\n"<<licz<<" "<<licz2<<"\n";
}