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
#include <cstdio>
#include <vector>

using ll = long long;

const int J = 7007;
const ll INF = 1e16;

int n, k, m;
std::vector<std::pair<int, ll>> jellies[J];
ll dp[2][J];
ll dist[J];

int main() {
    scanf("%d%d%d", &n, &k, &m);

    for (int i = 0; i < n; i++) {
        int ki, mi, ci;
        scanf("%d%d%d", &ki, &mi, &ci);
        jellies[ki].push_back(std::make_pair(mi, ci));
    }

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < m; j++)
            dp[i][j] = INF;

    dp[0][0] = 0;

    int b = 0;

    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < m; j++)
            dp[1 - b][j] = INF;

        for (int j = 0; j < m; j++) {
            if (dp[b][j] == INF)
                continue;

            for (std::pair<int, ll> p : jellies[i]) {
                int r = j + p.first;

                if (r >= m)
                    r -= m;

                dp[1 - b][r] = std::min(dp[1 - b][r], dp[b][j] + p.second);
            }
        }

        b = 1 - b;
    }

    std::vector<std::pair<int, ll>> edges;

    for (int i = 0; i < m; i++)
        if (dp[b][i] < INF)
            edges.push_back(std::make_pair(i, dp[b][i]));

    std::vector<int> queue;

    for (int i = 0; i < m; i++) {
        dist[i] = INF;
        queue.push_back(i);
    }

    dist[0] = 0;

    while (!queue.empty()) {
        int u = queue[0];
        int i = 0;
        ll min_dist = dist[u];

        for (int j = 0; j < queue.size(); j++) {
            int v = queue[j];

            if (dist[v] < min_dist) {
                min_dist = dist[v];
                u = v;
                i = j;
            }
        }

        queue.erase(queue.begin() + i);

        for (std::pair<int, ll> p : edges) {
            int v = u + p.first;

            if (v >= m)
                v -= m;

            ll alt = dist[u] + p.second;

            if (alt < dist[v])
                dist[v] = alt;
        }
    }

    for (int i = 0; i < m; i++) {
        if (dist[i] < INF)
            printf("%lld\n", dist[i]);
        else
            printf("-1\n");
    }

    return 0;
}