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
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const ll inf = 1e18;

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

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

	vector<vector<pair<int, int>>> kol(k);
	for(int i = 0; i < n; ++i) {
		int a, s, w;
		cin >> a >> s >> w;
		a--; s %= m;
		kol[a].eb(mp(s, w));
	}

	vector<ll> c(m, inf);
	c[0] = 0LL;
	for(int i = 0; i < k; ++i) {
		vector<ll> c1(m, inf);
		for(auto [s, w] : kol[i]) {
			for(int j = 0; j < m; ++j) {
				int x = (j+s < m ? j+s : j+s-m);
				c1[x] = min(c1[x], c[j] + w);
			}
		}

		c = c1;
	}

	vector<pair<ll, int>> e;
	for(int j = 0; j < m; ++j) {
		if(c[j] < inf) e.eb(mp(c[j], j));
	}

	vector<ll> dist(m, inf);
	priority_queue<pair<ll, int>> q;
	dist[0] = 0LL;
	q.push({0LL, 0});

	while(!q.empty()) {
		auto [d, v] = q.top(); q.pop();
		d = -d;

		if(d > dist[v]) continue;
		for(auto [cost, j] : e) {
			int u = (v+j < m ? v+j : v+j-m);
			if(dist[v] + cost < dist[u]) {
				dist[u] = dist[v] + cost;
				q.push({-dist[u], u});
			}
		}
	}

	for(ll &x : dist) cout << (x < inf ? x : -1) << '\n';

	return 0;
}