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
#include<bits/stdc++.h>
using namespace std;

typedef pair<long long, long long> par;
vector<par> col[7009], edges;
priority_queue<par, vector<par>, greater<par> > q;
long long dp[2][7009], wyn[7009];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	long long n, k, m, a, b, c;
	par p, e;
	cin>>n>>k>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>a>>b>>c;
		col[a].push_back(par(b, c));
	}
	for(int i=1; i<=k; i++)
	{
		if(col[i].size() == 0)
		{
			cout<<"0\n";
			for(int j=1; j<m; j++) cout<<"-1\n";
			return 0;
		}
	}
	for(int i=0; i<m; i++) wyn[i] = dp[0][i] = dp[1][i] = (1LL<<60);
	dp[0][0] = wyn[0] = 0;
	
	for(int j=1; j<=k; j++)
	{
		for(int l=0; l<col[j].size(); l++)
		{
			p = col[j][l];
			for(int x=0; x<m; x++)
			{
				if(dp[0][x] < (1LL<<60))
				{
					a = (x + p.first) % m;
					b = dp[0][x] + p.second;
					if(dp[1][a] > b) dp[1][a] = b;
				}
			}
		}
		for(int l=0; l<m; l++) 
		{
			dp[0][l] = dp[1][l];
			dp[1][l] = (1LL<<60);
		}
	}
	for(int i=0; i<m; i++) if(dp[0][i] < (1LL<<60)) edges.push_back(par(dp[0][i], i));
	
	q.push(par(0, 0));
	while(!q.empty())
	{
		p = q.top();
		q.pop();
		if(p.first > wyn[p.second]) continue;
		for(int j=0; j<edges.size(); j++)
		{
			e = edges[j];
			a = (p.second + e.second) % m;
			b = p.first + e.first;
			if(wyn[a] > b)
			{
				wyn[a] = b;
				q.push(par(b, a));
			}
		}
	}
	
	for(int i=0; i<m; i++)
	{
		if(wyn[i] == (1LL<<60)) cout<<"-1\n";
		else cout<<wyn[i]<<"\n";
	}
    return 0;
}