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

#define ll long long

constexpr int maxn = 7002;
constexpr ll inf = 1000000000000000000;

int n,k,m, kol[maxn], masa[maxn];
vector <pair<int,ll>> con;
vector <int> ls[maxn];
ll koszt[maxn], dp[2][maxn], dis[maxn];
bool vis[maxn];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> k >> m;
	for(int i=1; i<=n; i++)
	{
		cin >> kol[i] >> masa[i] >> koszt[i];
		ls[kol[i]].push_back(i);
	}

	for(int i=0; i<=1; i++)
		for(int r=0; r<m; r++) 
			dp[i][r] = inf;

	dp[0][0] = dp[1][0] = 0;
	for(int i=1; i<=k; i++)
	{
		for(int r=0; r<m; r++) dp[i&1][r] = inf;

		for(auto x : ls[i])
			for(int r=0; r<m; r++)
				dp[i&1][(r+masa[x])%m] = min(dp[i&1][(r+masa[x])%m], dp[(i-1)&1][r]+koszt[x]);
	}

	for(int r=1; r<m; r++)
		if(dp[k&1][r] != inf) con.push_back({r, dp[k&1][r]});

	for(int i=0; i<m; i++) dis[i] = inf;

	dis[0] = 0;
	for(int i=0; i<m; i++)
	{
		int v = -1;
		for(int j=0; j<m; j++)
			if(!vis[j] && (v == -1 || dis[j] < dis[v]))
				v = j;

		if(dis[v] == inf) break;

		vis[v] = 1;
		for(auto ed : con)
		{
			int u = (v+ed.first)%m;
			ll c = ed.second;
			if(dis[v]+c<dis[u]) dis[u]=dis[v]+c;
		}
	}

	for(int i=0; i<m; i++)
	{
		if(dis[i] == inf) cout << "-1\n";
		else cout << dis[i] << '\n';
	}
}