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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e16;
const int MAXN = 7e3 + 7;
int n, k, m;
vector<pair<int, int>> g[MAXN]; //[i] <- kolor i, .first masa, .second cena
ll dist[MAXN][MAXN];

void dijkstra(){
	priority_queue<pair<ll, pair<int, int>>> q;
	q.push({0, {0, 0}});

	ll d;
	int v, j, nxt;
	while(q.size()){
		d = -q.top().first;
		v = q.top().second.first;
		j = q.top().second.second;
		q.pop();

		if(d != dist[v][j]){
			continue;
		}

		nxt = j % k + 1;
		for(auto&[ms, price] : g[nxt]){
			if(dist[(v + ms) % m][nxt] > (ll)dist[v][j] + price){
				dist[(v + ms) % m][nxt] = (ll)dist[v][j] + price;
				q.push({-dist[(v + ms) % m][nxt], make_pair((v + ms) % m, nxt)});
			}
		}
	}
}

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

	cin >> n >> k >> m;
	for(int i = 1; i <= n; i++){
		int ki, mi, ci;
		cin >> ki >> mi >> ci;

		g[ki].push_back({mi, ci});
	}

	for(int i = 0; i < m; i++){
		for(int j = 1; j <= k; j++){
			dist[i][j] = INF;
		}
	}

	dijkstra();

	cout << 0 << '\n';
	for(int i = 1; i < m; i++){
		if(dist[i][k] >= INF){
			cout << -1 << '\n';
		}else{
			cout << dist[i][k] << '\n';
		}
	}


	return 0;
}