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
#include <array>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <ios>
#include <queue>

#pragma GCC optimize ("O3")

#define int long long

using namespace std;

int32_t main(){
    
    cin.tie(0);
    std::ios_base::sync_with_stdio(0);

    int n, k, m;
    cin>>n>>k>>m;

    vector<vector<array<int, 2>>> zel(k);
   
    for(int i=0;i<n;i++){
        int a, b, c;
        cin>>a>>b>>c;
        zel[a-1].push_back({b, c});
    }

    vector<vector<int>> dist(m, vector<int>(k+1, LLONG_MAX));
    dist[0][0] = 0; 
    
    for(int k0=0;k0<k;k0++){
        for(int r=0;r<m;r++) if(dist[r][k0] < LLONG_MAX){
            for(auto z:zel[k0]){
                auto& d_ref = dist[(r+z[0])%m][k0+1];
                d_ref = min(d_ref, dist[r][k0] + z[1]);
            }
        }
    }

    vector<array<int,2>> moves;
    for(int i=0;i<m;i++) if(dist[i][k] < LLONG_MAX)
        moves.push_back({i, dist[i][k]});
       
    //cerr<<"moves:"; for(auto m:moves) cerr<<m[0]<<":"<<m[1]<<", "; cerr<<endl; 
    vector<int> dist2(m, LLONG_MAX);
    dist2[0]=0;

    int vis_thr=0;

    vector<int> vis(m,0);

    for(auto move:moves){
        vis_thr+=2;
        for(int i=0;i<m;i++) if(vis[i]<vis_thr){
            int j = i;
            while(vis[j]<vis_thr){
                int next = (j+move[0]);
                if(next>=m) next -=m;

                auto& d_next = dist2[next];
                auto& d_this = dist2[j];

                if(d_this<LLONG_MAX) d_next = min(d_next, d_this + move[1]);
                
                vis[j]++;
                j = next;
            }
        }
    }
    


    cerr<<"end"<<endl;
    //for(int i=0;i<m;i++) for(int j=0;j<k;j++)
        //cout<<"dist["<<i<<"]["<<j<<"]="<<dist[i][j]<<endl;



    for(int i=0;i<m;i++){
        int d = dist2[i];
        if(d==LLONG_MAX) cout << "-1";
        else cout << d;
        cout << endl;
    }






}