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
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,int> pli;
const int MX=7070;
int k,n,m,x,y,z;
long long f[2][MX];
vector<pli> v[MX],steps;
int main() {
  scanf("%d%d%d",&k,&n,&m);
  for (int i=0; i<k; i++) {
    scanf("%d%d%d",&x,&y,&z);
    v[x].emplace_back(z,y%m);
  }
  memset(f,120,sizeof(f));
  long long inf=f[0][0];
  f[0][0]=0;
  for (int i=1; i<=n; i++) {
    int cur=(i&1);
    int prv=(cur^1);
    memset(f[cur],120,sizeof(f[cur]));
    for (int j=0; j<m; j++) if (f[prv][j]<inf)
      for (int k=0; k<v[i].size(); k++) {
        int nxt=j+v[i][k].second;
        if (nxt>=m) nxt-=m;
        f[cur][nxt]=min(f[cur][nxt],f[prv][j]+v[i][k].first);
      }
  }
  int lst=(n&1);
  f[lst][0]=0;
  priority_queue<pli,vector<pli>,greater<pli>> q;
  for (int i=1; i<m; i++) if (f[lst][i]<inf) {
    steps.emplace_back(f[lst][i],i);
    q.push({f[lst][i],i});
  }
  while (!q.empty()) {
    long long dst=q.top().first;
    int i=q.top().second;
    q.pop();
    if (f[lst][i]!=dst) continue;
    for (int j=0; j<steps.size(); j++) {
      long long cost=dst+steps[j].first;
      int nxt=i+steps[j].second;
      if (nxt>=m) nxt-=m;
      if (cost<f[lst][nxt]) {
        f[lst][nxt]=cost;
        q.push({cost,nxt});
      }
    }
  }
  for (int i=0; i<m; i++) printf("%lld\n",(f[lst][i]<inf)?f[lst][i]:-1LL);
  return 0;
}