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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//
// Created by piotr on 13.03.2024.
//
#include <ctime>
#include <cassert>
#include <cstdio>
#include <map>
#include <queue>
#include <vector>

const long long MAX_CENA = 1000000000000000000ll;

struct Zelki
{
	int masa;
	long long cena;

	bool operator<(const Zelki& inny) const {
		return cena > inny.cena;
	}
};

std::vector<long long> generate_modulos(const int M, const std::vector<Zelki>& kolorowe) {
	std::vector<long long> C(M, MAX_CENA);
	for (const Zelki& z : kolorowe) {
		int modulo = z.masa % M;
		C[modulo] = std::min(C[modulo], z.cena);
	}
	return C;
}

std::vector<long long> merge_modulos(const int M, const std::vector<long long>& x, const std::vector<Zelki>& kolorowe) {
	std::vector<long long> C(M, MAX_CENA);
	for (int i=0; i<M; ++i) {
		for (const Zelki& z : kolorowe) {
			int modulo = (i + z.masa) % M;
			C[modulo] = std::min(C[modulo], x[i] + z.cena);
		}
	}
	return C;
}

int main() {
	int N, K, M;
	assert(scanf("%d%d%d", &N, &K, &M) == 3);

	std::vector<Zelki> kolorami[K];
	for (int n=0; n<N; ++n) {
		int kolor, masa; long long cena;
		assert(scanf("%d%d%lld", &kolor, &masa, &cena) == 3);
		kolorami[kolor-1].push_back({masa, cena});
	}

	std::vector<long long> modulos = generate_modulos(M, kolorami[0]);
	for (int k=1; k<K; ++k) {
		modulos = merge_modulos(M, modulos, kolorami[k]);
	}

	std::vector<Zelki> zestawy;
	zestawy.reserve(M);
	for (int m=1; m<M; ++m) {
		if (modulos[m] < MAX_CENA) {
			zestawy.push_back({m, modulos[m]});
		}
	}

	std::vector<long long> ceny(M, MAX_CENA);
	ceny[0] = 0;

	// OK, teraz czas na algorytm grafowy
	std::priority_queue<Zelki> pq;
	pq.push({0, 0});
	while (!pq.empty()) {
		int cena = pq.top().cena;
		int m0 = pq.top().masa;
		pq.pop();

		if (cena > ceny[m0]) {
			continue;
		}

		for (const Zelki& zestaw : zestawy) {
			int m = (m0 + zestaw.masa) % M;
			if (ceny[m0] + zestaw.cena < ceny[m]) {
				ceny[m] = ceny[m0] + zestaw.cena;
				pq.push({m, ceny[m]});
			}
		}
	}

	for (int m=0; m<M; ++m) {
		printf("%lld\n", ceny[m] < MAX_CENA ? ceny[m] : -1);
	}
}