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
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
ll maxn=7003, N, K, M, inf=1e17+999;
vector<ll> ans(maxn, inf);
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K >> M;
    vector<vector<pair<ll, ll>>> v(maxn);
    ans[0]=0;
    for (int i=0; i<N; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        b%=M;
        if (K==1) ans[b]=min(ans[b], c);
        v[a].push_back({b, c});
    }
    for (int i=1; i<=K; i++) {
        if (v[i].empty()) {
            cout << "0" << "\n";
            for (int j = 1; j < M; j++) {
                cout << "-1" << "\n";
            }
            return 0;
        }
        sort(v[i].begin(), v[i].end());
    }

    for (int i=1; i<=K; i++) {
        for (int j=1; j<v[i].size(); j++){
            if (v[i][j-1].f==v[i][j].f){
                v[i][j-1].s=min(v[i][j].s, v[i][j-1].s);
                v[i].erase(v[i].begin() + j);
                j--;
            }
        }
    }

    vector<pair<ll, ll>> ost=v[1];
    for (int i = 2; i <= K; i++) {
        vector<pair<ll, ll>> pop, vis(M+1, {inf, inf});
        ll ov=0;
        for (int j = 0; j < v[i].size(); j++) {
            for (int k = 0; k < ost.size(); k++) {
                ll r = v[i][j].f + ost[k].f, z = v[i][j].s + ost[k].s;
                r%=M;
                if (i!=K && vis[r].f>z) {
                    vis[r].f=z;
                    if (vis[r].s!=inf){
                        pop[vis[r].s].s=z;
                    }
                    else {
                        vis[r].s=ov;
                        pop.push_back({r, z});
                        ov++;
                    }
                }
                if (i==K && ans[r]>z) {
                    ans[r]=z;
                    pop.push_back({r, z});
                }
            }
        }
        ost=pop;
    }
    vector<pair<ll, ll>> vis(M+1, {inf, inf});
    while (!ost.empty()) {
        for (int i = 1; i <= K; i++) {
            vector<pair<ll, ll>> pop;
            vector<int> visR;
            ll ov=0;
            for (int j = 0; j < v[i].size(); j++) {
                for (int k = 0; k < ost.size(); k++) {
                    ll r = v[i][j].f + ost[k].f, z = v[i][j].s + ost[k].s;
                    r%=M;
                    if (i!=K && vis[r].f>z) {
                        visR.push_back(r);
                        vis[r].f=z;
                        if (vis[r].s!=inf){
                            pop[vis[r].s].s=z;
                        }
                        else {
                            vis[r].s=ov;
                            pop.push_back({r, z});
                            ov++;
                        }
                    }
                    if (i==K && ans[r]>z) {
                        ans[r]=z;
                        pop.push_back({r, z});
                    }
                }
            }
            for (int r = 0; r < visR.size(); r++) {
                vis[visR[r]] = {inf, inf};
            }
            ost=pop;
        }
    }

    for (int i=0; i<M; i++){
        if (ans[i]==inf) ans[i]=-1;
        cout << ans[i] << "\n";
    }
    return 0;
}