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
#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

int n,k,m;

long long a[7100];
map<int, long long> tab[7100];

void wylicz_a() {
    long long dp[2][m]; //dp[indeks_koloru][reszta_przez_m]
    
    for(int j=0;j<m;j++) dp[0][j] = -1;
    for (pair<int, int> w : tab[0])
        dp[0][w.first] = w.second;
    
    
    for(int i=1;i<k;i++) {
        for(int j=0;j<m;j++) {
            dp[i%2][j] = -1;
            for (pair<int, int> w : tab[i]) {
                long long s = dp[(i+1)%2][(j-w.first+m)%m];

                //cout<<"abc "<<s<<" "<<(i-1)<<" "<<(j-w.first+m)%m<<endl;
                if(s != -1) {
                    if(dp[i%2][j] == -1) dp[i%2][j] = s+w.second;
                    else dp[i%2][j] = min(dp[i%2][j], s+w.second);
                    //cout<<"Zmodyfikowano "<<i<<", "<<j<<"na "<<dp[i%2][j]<<endl;
                }
            }
        }
    }
    
    for(int i=0;i<m;i++) a[i] = dp[(k-1)%2][i];
    a[0] = 0;
    
    //for(int i=0;i<m;i++) cout<<a[i]<<endl;
    //cout<<endl<<endl;
    
}

bool uzyte[7100];

void ostateczne_obliczenia() {
    int naj_idx;
    for(int runda=0;runda<m;runda++) {
        naj_idx = -1;
        for(int i=0;i<m;i++) {
            if(uzyte[i] || a[i] == -1) continue; 
            if(naj_idx == -1) naj_idx = i;
            else if(a[naj_idx] > a[i]) naj_idx = i;
        }
        if(naj_idx == -1) break;
        
        uzyte[naj_idx] = true;
        //cout<<"asdf: "<<naj_idx<<" "<<uzyte[naj_idx]<<endl;
        
        for(int i=0;i<m;i++) {
            if(a[i] == -1) continue;
            if(a[(i+naj_idx)%m] == -1) a[(i+naj_idx)%m] = a[i]+a[naj_idx];
            else a[(i+naj_idx)%m] = min(a[i]+a[naj_idx], a[(i+naj_idx)%m]);
            //cout<<i+naj_idx<<": "<<a[(i+naj_idx)%m]<<endl;
        }
    }
    
    for(int i=0;i<m;i++) cout<<a[i]<<endl;
}

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

    cin>>n>>k>>m;
    
    int ki, mi;
    long long ci;
    for(int i=0;i<n;i++) {
        cin>>ki>>mi>>ci;
        ki--;
        mi %= m;
        if(tab[ki].find(mi) == tab[ki].end()) tab[ki][mi] = ci;
        else tab[ki][mi] = min(tab[ki][mi], ci);
    }
    
    wylicz_a();
    ostateczne_obliczenia();
    
    return 0;
}