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<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

#define S 7007

using namespace std;
typedef long long ll;
ll inf = 1'000'000'000'000'000'000;
int M[S];
int C[S];

vector<int> V[S];

ll dp[S];
ll tmp[S];

int m;

ll dp2[S];
ll ans[S];

int main(void){
    int n,k;
    scanf("%d %d %d",&n,&k,&m);
    for(int i = 1; i <= n; i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        M[i] = b % m;
        C[i] = c;
        V[a].push_back(i);
    }

    dp[0] = 0;
    tmp[0] = inf;
    for(int i = 1; i <= m; i++){
        dp[i] = inf;
        tmp[i] = inf;
    }

    for(int i = 1; i <= k; i++){
        for(int j = 0; j < V[i].size(); j++){
            int v = V[i][j];
            for(int l = 0; l < m; l++){
                if(l + M[v] >= m){
                    tmp[l + M[v] - m] = min(tmp[l + M[v] - m], dp[l] + C[v]);
                }else{
                    tmp[l + M[v]] = min(tmp[l + M[v]], dp[l] + C[v]);
                }
                
            }
        }

        for(int j = 0; j < m; j++){
            dp[j] = tmp[j];
            tmp[j] = inf;
        }
    }
    for(int i = 0; i < m; i++){
        dp2[i] = inf;
    }

    for(int i = 0; i < m; i++){
        if(dp[i] < inf){
            ll p = dp[i];
            int e = 0;
            for(int j = 1; j < m; j++){
                e += i;
                if(e >= m)
                    e -= m;
                dp2[e] = min(dp2[e], p);
                p += dp[i];
            }
        }   
    }

    for(int i = 0; i < m; i++){
        ans[i] = inf;
    }
    
    ans[0] = 0;
    for(int i = 0; i < m; i++){
        if(dp2[i] < inf){
            for(int j = 0; j < m; j++){
                if(i + j >= m){
                    ans[i + j - m] = min(ans[i + j - m], ans[j] + dp2[i]);
                }else {
                    ans[i + j] = min(ans[i + j], ans[j] + dp2[i]);
                }
            }
        }
    }

    for(int i = 0; i < m; i++){
        if(ans[i] < inf){
            printf("%lld\n",ans[i]);
        }else{
            printf("-1\n");
        }
    }

    return 0;
}