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
#include<stdio.h>
#include<vector>
#define N 7009
#define pr pair<int,int> 
#define int long long
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,mod,f[N],g[N];vector<pr>a[N];bool v[N];
main()
{
	read(n);read(m);read(mod);
	for(int u,v,w;n--;)read(u),read(v),read(w),a[u].emplace_back(v,w);
	for(int i=1;i<mod;f[i++]=1ll<<60);
	for(int i=1;i<=m;++i)
	{
		for(int j=0;j<mod;g[j++]=1ll<<60);
		for(int j=0;j<a[i].size();++j)for(int k=0;k<mod;++k)
			g[(k+a[i][j].first)%mod]=min(g[(k+a[i][j].first)%mod],
				f[k]+a[i][j].second);
		for(int j=0;j<mod;f[j]=g[j],++j);
	}
	g[0]=0;for(int j=1;j<mod;g[j++]=1ll<<60);
	for(int o=mod,i,minn;o--;)
	{
		minn=1ll<<60;
		for(int j=0;j<mod;++j)if(!v[j])if(g[j]<minn)minn=g[j],i=j;
		v[i]=1;
		for(int j=0;j<mod;++j)g[(i+j)%mod]=min(g[(i+j)%mod],g[i]+f[j]);
	}
	for(int i=0;i<mod;++i)printf("%lld\n",g[i]<1ll<<60?g[i]:-1);
}