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
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using std::cin, std::cout, std::vector;

void init_io() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

constexpr std::uint64_t infinite_cost = std::numeric_limits<std::uint64_t>::max() / 4;

struct Edge {
  unsigned mass;
  unsigned cost;
};

struct State {
  std::uint64_t cost;
  bool done;
};

class Graph {
public:
  void read() {
    cin >> num_edges >> num_colors >> mass_range;
    edges_for_color.resize(num_colors);
    for (unsigned i=0; i<num_edges; ++i) {
      unsigned color;
      Edge edge;
      cin >> color >> edge.mass >> edge.cost;
      --color;
      if (edge.mass == mass_range) edge.mass = 0;
      edges_for_color[color].push_back(edge);
    }
  }

  // O(num_edges * mass_range)
  void calc_big_edges() {
    big_edges.assign(mass_range, infinite_cost);
    big_edges[0] = 0;
    vector<std::uint64_t> next_big_edges(mass_range);

    for (const auto &edges : edges_for_color) {
      next_big_edges.assign(mass_range, infinite_cost);
      for (const auto edge : edges) {
        unsigned new_mass = edge.mass;
        for (const auto big_edge : big_edges) {
          auto &next_big_edge = next_big_edges[new_mass];
          next_big_edge = std::min(next_big_edge, big_edge + edge.cost);
          ++new_mass;
          if (new_mass == mass_range) new_mass = 0;
        }
      }

      big_edges.swap(next_big_edges);
    }
  }

  // O(mass_range^2)
  void solve() {
    {
      State initial;
      initial.cost = infinite_cost;
      initial.done = false;
      states.assign(mass_range, initial);
    }

    states[0].cost = 0;

    for (;;) {
      unsigned best_mass = -1u;
      std::uint64_t best_cost = infinite_cost;
      for (unsigned mass = 0; mass < mass_range; ++mass) {
        const State &state = states[mass];
        if (!state.done && state.cost < best_cost) {
          best_mass = mass;
          best_cost = state.cost;
        }
      }
      if (best_mass == -1u) break;
      states[best_mass].done = true;
      unsigned new_mass = best_mass;
      for (const auto edge_cost : big_edges) {
        auto &new_state = states[new_mass];
        new_state.cost = std::min(new_state.cost, best_cost + edge_cost);
        ++new_mass;
        if (new_mass == mass_range) new_mass = 0;
      }
    }
  }

  void print() const {
    for (const auto &state : states) {
      if (state.cost == infinite_cost) {
        cout << "-1\n";
      } else {
        cout << state.cost << "\n";
      }
    }
  }

private:
  unsigned num_edges;
  unsigned num_colors;
  unsigned mass_range;
  vector<vector<Edge>> edges_for_color;

  // [mass] -> cost
  vector<std::uint64_t> big_edges;

  // [mass]
  vector<State> states;
};

int main() {
  init_io();

  Graph graph;
  graph.read();
  graph.calc_big_edges();
  graph.solve();
  graph.print();
}