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
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,k,m;
	cin>>n>>k>>m;
	vector<vector<pair<int,long long int>>>t(k+1);
	int a,b;
	long long int c;
	for(int i=0; i<n; i++)
	{
		cin>>a>>b>>c;
		t[a].push_back({b,c});
	}
	int il=0;
	for(int i=1; i<=k; i++)
		if(t[i].size())
			il++;
	if(il<k)
	{
		cout<<"0\n";
		for(int i=1; i<m; i++)
			cout<<"-1\n";
		return 0;
	}
	vector<vector<long long int>>t1(2,vector<long long int>(m,-1));
	t1[0][0]=0;
	for(int i=0; i<k; i++)
	{
		int c1=i%2,c2=1-c1;
		for(int i1=0; i1<m; i1++)
			t1[c2][i1]=-1;
		for(auto j:t[i+1])
			for(int i1=0; i1<m; i1++)
			{
				if(t1[c1][i1]>=0)
				{
					int c3=(i1+j.first)%m;
					if(t1[c2][c3]!=-1)
						t1[c2][c3]=min(t1[c2][c3],t1[c1][i1]+j.second);
					else
						t1[c2][c3]=t1[c1][i1]+j.second;
				}
			}
	}
	vector<long long int>cst(m,-1);
	for(int i=0; i<m; i++)
		cst[i]=t1[k%2][i];
	vector<long long int>cstg(m,-1);
	cstg[0]=0;
	for(int i=0; i<m; i++)
	{
		if(cst[i]==-1)
			continue;
		long long int pom=cst[i];
		int pom2=i;
		while(pom2!=0)
		{
			if(cstg[pom2]==-1)
				cstg[pom2]=pom;
			else
				cstg[pom2]=min(cstg[pom2],pom);
			pom+=cst[i];
			pom2=(pom2+i)%m;
		}
	}
	vector<long long int>csto(m,-1);
	csto[0]=0;
	for(int i=0; i<m; i++)
	{
		if(cstg[i]==-1)
			continue;
		for(int j=0; j<m; j++)
			if(csto[j]!=-1)
			{
				int p=(j+i)%m;
				if(csto[p]==-1)
					csto[p]=csto[j]+cstg[i];
				else
					csto[p]=min(csto[p],csto[j]+cstg[i]);
			}
	}
	for(auto i:csto)
		cout<<i<<"\n";
}