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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
ll inf=1000000000000000000ll;

int INT() {
	int in; scanf("%d", &in);
	return in;
}

struct zelek {
	int m;
	ll c;
};

struct info {
	ll d;
	int x;

	bool operator < (const info i) const {
		return d>i.d;
	}
};

int main() {
	int n=INT(), K=INT(), M=INT();
	vector <vector <zelek> > zelki(K+1);
	for(int i=0; i<n; ++i) {
		int k=INT(), m=INT(), c=INT();
		zelki[k].pb({m, ll(c)});
	}
	vector <ll> cost(M, inf);
	cost[0]=0ll;
	for(int k=1; k<=K; ++k) {
		vector <ll> cost2(M, inf);
		swap(cost, cost2);
		for(zelek &i : zelki[k]) for(int m=0; m<M; ++m) cost[(m+i.m)%M]=min(cost[(m+i.m)%M], cost2[m]+i.c);
	}
	//for(int m=0; m<M; ++m) printf("%lld ", cost[m]);
	//printf("\n");

	vector <ll> ans(M, inf);
	ans[0]=0ll;
	priority_queue <info> pq;
	pq.push({0ll, 0});
	while(!pq.empty()) {
		int x=pq.top().x;
		pq.pop();

		ll d=ans[x];
		for(int m=1; m<M; ++m) {
			int u=x+m;
			if(u>=M) u-=M;
			if(ans[u]>d+cost[m]) ans[u]=d+cost[m], pq.push({ans[u], u});
		}
	}
	for(int m=0; m<M; ++m) {
		if(ans[m]==inf) printf("-1\n");
		else printf("%lld\n", ans[m]);
	}
	exit(0);
}