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
 95
 96
 97
 98
 99
100
101
102
103
104
105
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define PPC(x) __builtin_popcountll(x)
#define MSB(x) (63 - __builtin_clzll(x))
#define LSB(x) __builtin_ctzll(x)
#define ARG(x, i) (get<i>(x))
#define ithBit(m, i) ((m) >> (i) & 1)
#define pb push_back
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#define CLR(x) x.clear(), x.shrink_to_fit()
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
 
template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b);	}
template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b);	}

const int maxN = 7007;
const long long INF = 1'000'000'000'000'000'000;

vector <pair <int, int> > bears[maxN];
vector <pair <int, long long> > E;
long long dp[2][maxN], dist[maxN];
bool vis[maxN];

void calcEdges(int k, int m)
{
	fill(&dp[0][0], &dp[0][m], INF);
	dp[0][0] = 0;

	FOR(i, 1, k+1)
	{
		auto* curr = &dp[i & 1][0];
		auto* prv = &dp[(i^1) & 1][0];

		fill(curr, curr + m, INF);

		for (auto& [w, c] : bears[i])
			FOR(j, 0, m)
				remin(curr[(j + w) % m], prv[j] + c);
	}

	auto* res = &dp[k & 1][0];
	FOR(i, 1, m)
		if (res[i] < INF)
			E.pb({ i, res[i] });
}

void calcDist(int m)
{
	fill(dist + 1, dist + m + 1, INF);
	FOR(_, 1, m)
	{
		int v = m;
		FOR(i, 0, m)
			if (!vis[i] and dist[i] < dist[v])
				v = i;
		if (v == m)
			break;
		vis[v] = true;

		for (auto& [d, c] : E)
			remin(dist[(v + d) % m], dist[v] + c);
	}
}

void solve()
{
	int n, k, m;
	scanf ("%d%d%d", &n, &k, &m);
	while (n--)
	{
		int color, weight, cost;
		scanf ("%d%d%d", &color, &weight, &cost);
		bears[color].push_back({ weight, cost });
	}

	calcEdges(k, m);
	calcDist(m);

	FOR(i, 0, m)
		printf("%lld\n", dist[i] < INF ? dist[i] : -1ll);
}

int main()
{
	int t = 1;
//	scanf ("%d", &t);	
	FOR(tid, 1, t+1)
	{
		//printf("Case #%d: ", tid);
		solve();
	}
	return 0;
}