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
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define ull unsigned long long

int m;
const ull UB=1e18;

struct opt{
    ull a[7000];
    opt() {
        for(int i=0; i<m; i++) a[i]=-1;
    }
    ~opt(){
    }
    void obcinaj(){
        for(int i=0; i<m; i++)
            if(a[i]>UB) a[i]=-1;
    }
    opt operator*(const opt& Pr) const{
        opt zwrot;
        for(int i=0; i<m; i++)
        for(int j=0; j<m; j++){
            if(Pr.a[j]!=-1 && a[(m+i-j)%m]!=-1)
                zwrot.a[i]=min(zwrot.a[i], Pr.a[j]+a[(m+i-j)%m]);
        }
        zwrot.obcinaj();
        return zwrot;
    }
    bool przypisz(const opt& Pr){
        bool zwrot=1;
        for(int i=0;i<m; i++){
            if(a[i]!=Pr.a[i]) zwrot=0;
            a[i]=Pr.a[i];
        }
        return zwrot;
    }
    bool kw(){
        return przypisz((*this)*(*this));
    }
    void skakaj(const vector<pair<int, ull>>& skoki){
        opt zmpom;
        for(int i=0; i<m; i++){
            for(int j=0; j<skoki.size(); j++){
                int skok = skoki[j].first;
                ull cena = skoki[j].second;
                if(a[(m+i-skok)%m]!=-1) zmpom.a[i]=min(zmpom.a[i], a[(m+i-skok)%m]+cena);
            }
        }
        przypisz(zmpom);
    }
};

void djk(const opt& kloc){
    bool odw[7000];
    for(int i =0; i<m; i++) odw[i]=0;
    //opt odl;
    ull odla[7000];
    for(int i=1; i<m; i++) odla[i]=-1;
    int wybrany=0;
    odla[0]=0;
    while(wybrany!=-1){
        odw[wybrany]=1;
        for(int i=1; i<m; i++)
        if(kloc.a[i]!=-1 && !odw[(wybrany+i)%m]){
            ull& x = odla[(wybrany+i)%m];
            ull y = odla[wybrany]+kloc.a[i];
            if(x>y) x=y;
            //odl.a[(wybrany+i)%m] = min(odl.a[(wybrany+i)%m], odl.a[wybrany]+kloc.a[i]);
        }
        wybrany=-1;
        ull najm=-2;
        for(int i=0; i<m; i++)
        if(!odw[i] && odla[i]<najm){
            najm=odla[i];
            wybrany=i;
        }
    }
    for(int i=0; i<m; i++)
        cout << (long long) odla[i] << endl;
}

int main()
{
    cin.sync_with_stdio(0); cin.tie(0);
    int n, k;
    scanf("%d %d %d", &n, &k, &m);
    vector<pair<int, ull>>* kolorki = new vector<pair<int, ull>>[k];
    for(int i=0; i<n; i++){
        int kolor, masa, cena;
        scanf("%d %d %d", &kolor, &masa, &cena);
        pair<int, ull> dodod;
        dodod.first=masa;
        dodod.second=cena;
        kolorki[kolor-1].push_back(dodod);
    }
    opt kloc;
    kloc.a[0]=0;
    for(int i=0; i<k; i++)
        kloc.skakaj(kolorki[i]);
    kloc.a[0]=0;
    //for(int i=0; i<13; i++) if(kloc.kw()) break;
    djk(kloc);
    return 0;
}