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
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
long long n,k,a,m,ko,ma,ce;
std::vector<std::vector<std::pair<long long,int>>>zel;
std::vector<long long>ceny;
std::vector<long long>ceny2;
const long long INF=1e17;
std::vector<std::pair<long long,int>>ce_ma;
int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cin>>n>>k>>m;
    zel.resize(k);
    ceny.resize(m,INF);
    ceny2.resize(m,INF);
    for(int i=0;i<n;i++){
        std::cin>>ko>>ma>>ce;
        zel[ko-1].emplace_back(ce,ma);
    }
    ceny[0]=0;

    for(int i=0;i<k;i++){
        for(int j=0;j<m;j++)
            ceny2[j]=INF;
        for(int j=0;j<m;j++)
            if(ceny[j]<INF){
                    //std::cerr<<"xx"<<j<<" "<<i<<" "<<zel[i].size()<<std::endl;

                for(auto x:zel[i]){
                    ceny2[(j+x.second)%m]=std::min(ceny2[(j+x.second)%m],ceny[j]+x.first);
                    }
                }
        std::swap(ceny,ceny2);
    }

    for(int i=1;i<m;i++){
        ce_ma.emplace_back(ceny[i],i);
    }
    std::sort(ce_ma.begin(),ce_ma.end());
    ceny[0]=0;
    for(auto x:ce_ma){
        for(int i=0;i<m;i++){
            int j=i;
            while(ceny[(j+x.second)%m]>ceny[j]+x.first){
                ceny[(j+x.second)%m]=ceny[j]+x.first;
                j=(j+x.second)%m;
            }
        }
    }
    for(int i=0;i<m;i++){
        std::cout<<(ceny[i]<INF?ceny[i]:-1)<<std::endl;
    }

}