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

#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define pii pair<int, int>
#define vi vector<int>
#define ll long long

#ifdef LOC
auto &operator << (auto &out, pair<auto, auto> a) {
	return out << "(" << a.st << ", " << a.nd << ")";
}

auto &operator << (auto &out, auto a) {
	out << "{";
	for (auto b : a)
		out << b << ", ";
	return out << "}";
}

void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }

#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif

const ll inf = 1e18;

int32_t main() {
   	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, k, m;
	cin >> n >> k >> m;
	vector<vector<pii> > z(k);
	rep(i, n) {
		int t, w, c;
		cin >> t >> w >> c;
		t --;
		if (w == m)
			w = 0;
		z[t].push_back({w, c});
	}
	vector<ll> dp(m, inf);
	vector<ll> tmp(m);
	dp[0] = 0;
	rep(t, k) {
		fill(all(tmp), inf);
		for (auto [w, c] : z[t]) {
			int p = w;
			rep(i, m) {
				if (dp[i] + c < tmp[p]) {
					tmp[p] = dp[i] + c;
				}
				p ++;
				if (p == m)
					p = 0;
			}
		}
		swap(tmp, dp);
	}
	dp[0] = 0;
	vi vis(m, 0);
	rep(i, m) {
		int p = -1;
		rep(j, m) {
			if (!vis[j] && dp[j] != inf && (p == -1 || dp[j] < dp[p])) {
				p = j;
			}
		}
		if (p == -1)
			break;
		vis[p] = 1;
		int pd = p;
		rep(j, m) {
			if (dp[p] + dp[j] < dp[pd])
				dp[pd] = dp[p] + dp[j];
			pd ++;
			if (pd == m)
				pd = 0;
		}
	}
	rep(i, m) {
		if (dp[i] == inf)
			cout << "-1\n";
		else
			cout << dp[i] << '\n';
	}
   	return 0;
}