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

#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(int i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define forx(v) for(int x=0; x<v; x++)
#define fory(v) for(int y=0; y<v; y++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = (ll)pow(10,18);
ll modulo = 998244353;
ld eps = 1e-13;
ifstream in;
ofstream out;

void deal(){
      ll n, k, m;
      cin>>n>>k>>m;
      
      vector<map<ll, ll> > bst(k);
      
      fori(n){
            ll ki, mi, ci;
            cin>>ki>>mi>>ci;
            --ki;
            mi %= m;
            if(bst[ki].find(mi) == bst[ki].end()){
                  bst[ki][mi] = inf;
            }
            bst[ki][mi] = min(bst[ki][mi], ci);
      }
      
      vector<ll> ans(m, inf);
      ans[0] = 0;
      fori(k){
            vector<ll> cur(m, inf);
            
            forj(m){
                  for(auto& el : bst[i]){
                        ll mi = el.ff, ci = el.ss;
                        ll id = (j - mi + m) % m;
                        if(ans[id] + ci < cur[j]){
                              cur[j] = ans[id] + ci;
                        }
                  }
            }
            
            ans = cur;
            
            /*
            fori(m){
                  cout<<ans[i]<<' ';
            }
            cout<<endl; */
      }
      
      ans[0] = 0;
      vector<bool> took(m, 0);
      fori(m){
            ll mn = inf;
            ll id = -1;
            fori(m){
                  if(ans[i] < mn && !took[i]){
                        mn = ans[i];
                        id = i;
                  }
            }
            
            if(id == -1){
                  break;
            }
            
            took[id] = 1;
            fori(m){
                  ans[(id + i) %m] = min(ans[(id + i) % m] , ans[id] + ans[i]);
            }
      }
      
      fori(m){
            if(ans[i] == inf){
                  ans[i] = -1;
            }
            cout<<ans[i]<<'\n';
      }
      
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}