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
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define gc getchar_unlocked
#define fi first
#define se second
#define inf 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;

void wczytaj(int &a){
	int c = gc();
	while(c < '0' || c > '9') c = gc();
	for(a = 0; c >= '0' && c <= '9'; c = gc()) a = a*10+c-'0';
}

void solve(){
	int n, k, m;
	wczytaj(n), wczytaj(k), wczytaj(m);
	vector<vector<pil>> kub(k);
	while(n--){
		int kol, mas, cen;
		wczytaj(kol), wczytaj(mas), wczytaj(cen);
		kub[kol-1].emplace_back(mas%m, cen);
	}
	
	vector<ll> dp(m, inf);
	dp[0] = 0ll;
	for(vector<pil> &vec : kub){
		vector<ll> nowy(m, inf);
		for(auto [mas, cen] : vec) REP(i, m){
			nowy[mas] = min(nowy[mas], dp[i]+cen);
			if(++mas == m) mas = 0;
		}
		swap(dp, nowy);
	}
	
	vector<bool> odw(m, 0);
	vector<ll> wyn(m, inf);
	wyn[0] = 0ll;
	REP(ile, m){
		int w = -1;
		REP(i, m) if(!odw[i] && (w<0 || wyn[i]<wyn[w])) w = i;
		odw[w] = 1;
		ll c = wyn[w];
		REP(i, m){
			wyn[w] = min(wyn[w], c+dp[i]);
			if(++w == m) w = 0;
		}
	}
	for(ll i : wyn) printf("%lld\n", i<inf ? i : -1ll);
}

int main(){
	solve();
	return 0;
}