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
109
110
111
#include <cstdio>
#include <unordered_map>
#include <vector>

typedef long long int i64;
const i64 INF = 1LL << 62;

struct Zel {
  int mass;
  i64 cost;
};

struct Node {
  int mass;
  i64 cost;
};

bool build_graph(int MOD, std::vector<std::vector<Zel>> &by_color, std::vector<Node> &output) {
  std::unordered_map<int, i64> a, b;
  std::unordered_map<int, i64> *curr = &a; // mass -> cost
  std::unordered_map<int, i64> *next = &b; // mass -> cost
  (*curr)[0] = 0;
  for (std::vector<Zel> with_color : by_color) {
    if (with_color.empty()) {
      return false;
    }
    next->clear();
    for (auto &node : *curr) {
      for (Zel &zel : with_color) {
        int new_mass = (node.first + zel.mass) % MOD;
        i64 new_cost = (node.second + zel.cost);
        if (!next->contains(new_mass) || (*next)[new_mass] > new_cost) {
          (*next)[new_mass] = new_cost;
        }
      }
    }
    std::unordered_map<int, i64> *tmp = next;
    next = curr;
    curr = tmp;
  }
  (*curr)[0] = 0;
  for (auto &node : *curr) {
    Node n = {.mass = node.first, .cost = node.second};
    // printf("%d %lld\n", n.mass, n.cost);
    output.push_back(n);
  }
  // exit(0);
  return true;
}

void discover(int MOD, std::vector<Node> &graph) {
  std::vector<i64> tab;
  for (int i = 0; i < MOD; ++i) {
    tab.push_back(INF);
  }
  for (Node &n : graph) {
    tab[n.mass] = n.cost;
  }
  bool diff = true;

  while (diff) {
    diff = false;
    for (int i = 1; i < MOD; ++i) {
      if (tab[i] != INF) {
        for (int j = i; j < MOD; ++j) {
          if (tab[j] != INF) {
            int t = (i + j) % MOD;
            i64 c = tab[i] + tab[j];
            if (tab[t] > c) {
              diff = true;
              tab[t] = c;
            }
          }
        }
      }
    }
  }

  for (int i = 0; i < MOD; ++i) {
    printf("%lld\n", tab[i] == INF ? -1 : tab[i]);
  }
}

int main() {
  int N, Colors, MOD;
  scanf("%d%d%d", &N, &Colors, &MOD);

  std::vector<std::vector<Zel>> by_color;

  for (int i = 0; i < Colors; ++i) {
    by_color.push_back(std::vector<Zel>());
  }

  for (int i = 0; i < N; ++i) {
    int color, mass, price;
    scanf("%d%d%d", &color, &mass, &price);
    Zel z = {.mass = mass % MOD, .cost = price};
    by_color[color - 1].push_back(z);
  }

  std::vector<Node> graph;
  if (!build_graph(MOD, by_color, graph)) {
    for (int i = 0; i < MOD; ++i) {
      puts(i ? "-1" : "0");
    }
  } else {
    discover(MOD, graph);
  }

  return 0;
}