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 <bits/stdc++.h>

#define pb push_back
#define st first
#define nd second

using ll = long long;
using ld = long double;

using namespace std;

const int N = 7005;

int n, k, m;

vector <pair<int, ll> > v[N];
ll wart1[N];
ll wart2[N];

ll ans[N];
bool visited[N];
vector <pair <int, ll> > krawedz;
priority_queue <pair <ll, int> > pq;

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

    cin >> n >> k >> m;
    for(int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].pb({b, c});
    }
    wart1[0] = 1;// wagi zwiekszone o 1
    for(int i = 1; i <= k; i++) {
        for(int ii = 0; ii < v[i].size(); ii++) {
            for(int iii = 0; iii < m; iii++) {
                if(wart1[iii]) {
                    int idx = (iii + v[i][ii].st) % m;
                    if(wart2[idx]) {
                        wart2[idx] = min(wart2[idx], wart1[iii] + v[i][ii].nd);
                    }
                    else {
                        wart2[idx] = wart1[iii] + v[i][ii].nd;
                    }
                }
            }
        }
        for(int ii = 0; ii < m; ii++) {
            wart1[ii] = wart2[ii];
            wart2[ii] = 0;
        }
    }
    for(int i = 0; i < m; i++) {
        wart1[i]--;
    }
    wart1[0] = 0;
    for(int i = 0; i < m; i++) {
        if(wart1[i] > 0) {
            krawedz.pb({i, wart1[i]});
        }
        ans[i] = -1;
    }
    
    ans[0] = 0;
    pq.push({0, 0});
    while(!pq.empty()) {
        int x = pq.top().nd;
        pq.pop();
        if(!visited[x]) {
            visited[x] = 1;
            for(int i = 0; i < krawedz.size(); i++) {
                int idx = (x + krawedz[i].st) % m;
                if(!visited[idx]) {
                    if(ans[idx] == -1) {
                        ans[idx] = ans[x] + krawedz[i].nd;
                        pq.push({-ans[idx], idx});
                    }
                    else if(ans[idx] > ans[x] + krawedz[i].nd){
                        ans[idx] = ans[x] + krawedz[i].nd;
                        pq.push({-ans[idx], idx});
                    }
                }
            }
        }
    }

    for(int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}