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
89
90
91
92
93
#include<bits/stdc++.h>

typedef long long in;
using namespace std;


struct ala{
	in poz;
	in wag;
};


struct comp{
	bool operator()(ala &a,ala &b)
	{
		return a.wag>b.wag;
	}
};




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	
	in a,b,c;
	cin>>a>>b>>c;
	in tab[c];
	for(in z=0;z<c;z++)tab[z]=-1;
	vector<vector<ala>>v(b+1);
	
	for(in z=0;z<a;z++)
	{
		in j,k,l;
		cin>>j>>k>>l;
		v[j].push_back({k,l});
	}
	for(in z=1;z<=b;z++)
	{
		if(v[z].size()==0)
		{
			cout<<"0\n";
			for(int w=1;w<c;w++)cout<<"-1\n";
			return 0;
		}
	}
	tab[0]=0;
	for(in z=1;z<=b;z++)
	{
		in tab2[c];
		for(in w=0;w<c;w++)tab2[w]=-1;
		for(in w=0;w<v[z].size();w++)
		{
			for(in x=0;x<c;x++)
			{
				if(tab[x]==-1)continue;
				in poz=x+v[z][w].poz;
				poz%=c;
				if(tab2[poz]==-1||tab2[poz]>tab[x]+v[z][w].wag)tab2[poz]=tab[x]+v[z][w].wag;
			}
		}
		for(in w=0;w<c;w++)tab[w]=tab2[w];
	}
	priority_queue<ala,vector<ala>,comp>q;
	q.push({0,0});
	in wyn[c];
	for(in z=0;z<c;z++)wyn[z]=-1;
	in m[c];
	in duz=1000000000000000000*9;
	for(in z=0;z<c;z++)
	{
		m[z]=duz;
	}
	while(!q.empty())
	{
		ala pom=q.top();
		q.pop();
		if(wyn[pom.poz]!=-1)continue;
		wyn[pom.poz]=pom.wag;
		for(in z=0;z<c;z++)
		{
			if(tab[z]==-1||wyn[(pom.poz+z)%c]!=-1||m[(pom.poz+z)%c]<=pom.wag+tab[z])continue;
			
			q.push({(pom.poz+z)%c,pom.wag+tab[z]});
			m[(pom.poz+z)%c]=pom.wag+tab[z];
		}
	}
	for(in z=0;z<c;z++)cout<<wyn[z]<<"\n";
	return 0;
}