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

using namespace std;
typedef long long ll;

const ll N = 7000 + 5, Inf = 0x3f3f3f3f3f3f3f3f;

inline ll gcd(ll x, ll y){
	if(y) return gcd(y, x % y);
	else return x;
}

inline void checkmin(ll &x, ll y){
	if(y < x) x = y;
}

class info{
public:
	ll v, w;
	inline info() {}
	inline info(ll v0, ll w0){
		v = v0, w = w0;
	}
};

ll n = 0, m = 0, k = 0, f[N][N] = {}, g[N] = {};
vector<info> bag[N] = {};

inline ll calc(ll x, ll y){
	if(x + y < m) return x + y;
	else return x + y - m;
}

int main(){
	scanf("%lld %lld %lld", &n, &k, &m);
	for(ll i = 0, c = 0, v = 0, w = 0 ; i < n ; i ++){
		scanf("%lld %lld %lld", &c, &v, &w); c --, v %= m;
		bag[c].push_back(info(v, w));
	}
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	for(ll c = 0 ; c < k ; c ++) for(auto node : bag[c]){
		ll v = node.v, w = node.w;
		for(ll x = 0 ; x < m ; x ++) checkmin(f[c + 1][calc(x, v)], f[c][x] + w);
	}
	memset(g, 0x3f, sizeof(g));
	g[0] = 0;
	for(ll v = 1 ; v < m ; v ++){
		ll w = f[k][v];
		for(ll i = 0, h = gcd(v, m) ; i < h ; i ++) for(ll j = i, t = 0 ; t < 2 * (m / h) ; j = calc(j, v), t ++) checkmin(g[calc(j, v)], g[j] + w);
	}
	for(ll i = 0 ; i < m ; i ++){
		if(g[i] < Inf) printf("%lld\n", g[i]);
		else printf("-1\n");
	}
	return 0;
}