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
#include <bits/stdc++.h>
using namespace std;
int n,k,m;
array<vector<array<long long,2>>,7001> v;
array<long long,7001> g,w;
array<long long,2> a;
array<bool,7001> c;
int t;
vector <int> r,rn;
vector<array<long long,2>> b;
long long ki,mi,ci,ww,i,j,a0,a1;
int main(){
	cin >> n >> k >> m;
	for(j=0;j<m;j++)
		w[j]=1e+18;
	for (i=0;i<n;i++){
		cin >> ki >> mi >> ci;
		v[ki].push_back({mi,ci});
	}
	//cout << "BB\n";
	//return 0;
	r={0};
	w[0]=0;
	for (i=1;i<=k;i++){
		for(auto j:r){
			g[j]=w[j];
			w[j]=1e+18;		
		}
		rn={};
		for (auto a:v[i]){
			a0=a[0];
			a1=a[1];
			for (auto j:r) {
				if(w[(a0+j)%m]==1e+18)
					rn.push_back((a0+j)%m);
				w[(a0+j)%m]=min(g[j]+a1,w[(a0+j)%m]);
				//cout << rn[0] << 'g'<<  g[j] << 'g' << w[(a0+j)%m] << '\n';
				}
			}
		r=rn;
		}
	t=1;
	w[0]=0;
	c[0]=true;
	//for(i=0;i<m;i++)
	//	cout << i << ' ' << w[i] << "\n";
	//cout <<"AAA\n";
	//return 0;
	while (t){
		ww=1e+18;
		i=-1;
		for (j=1;j<m;j++){
			if (w[j]<ww and !c[j]){
				i=j;
				ww=w[j];
			}
		}
		if (i>=0){
			c[i]=1;
			b.push_back({ww,i});
			for (auto a:b){
				if (!c[(i+a[1])%m])
					w[(i+a[1])%m]=min(w[(i+a[1])%m],ww+a[0]);
				}
			}
		else
			break;
		}

	for (i=0;i<m;i++){
		if (c[i])
			cout << w[i] << '\n';
		else
			cout << -1 << '\n';
		}
	}