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
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;

const int MAXN = 7e3+7;
vector<pair<int, int>> zel[MAXN]; // <cena, waga>
bool done[MAXN];
ll rozw[MAXN];
priority_queue<pair<ll, int>> q; // <-cena, mod> 

void propagade(const int &k, const int &ck, const int& m, const ll &c, const int &mod){
	if(ck == k){
		if(!done[mod]) q.push(make_pair(-c, mod));
		return;
	}

	for(auto& [cost, w] : zel[ck]){
		propagade(k, ck+1, m, c+cost, (mod+w)%m);
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k, m;
	cin >> n >> k >> m;

	for(int i = 0; i < m; i++) rozw[i] = LLONG_MAX;

	for(int i = 0; i < n; i++){
		int ki, mi, ci;
		cin >> ki >> mi >> ci;
		zel[ki-1].push_back(make_pair(ci, mi));
	}

	//validate if there is enought zel
	for(int i = 0; i < k; i++) if((int)zel[i].size() == 0){
		cout << 0 << '\n';
		for(int i = 1; i < m; i++) cout << -1 << '\n';
		return 0;
	}

	for(int i = 0; i < k; i++) sort(zel[i].begin(), zel[i].end());

	q.push(make_pair(0, 0));

	while(!q.empty()){
		pair<ll, int> cur = q.top();
		q.pop();

		if(done[cur.nd]) continue;

		ll c = -cur.st;
		int mod = cur.nd;

		//cout << "c: " << c << " mod: " << mod << '\n';

		done[mod] = true;
		rozw[mod] = c;

		propagade(k, 0, m, c, mod);
	}

	for(int i = 0; i < m; i++){
		if(!done[i]) cout << -1 << '\n';
		else cout << rozw[i] << '\n';
 	}

	return 0;
}