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
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n, k, m; cin >> n >> k >> m;
    vector<vector<T>>a(k+1);
    for (int i = 0; i<n; i++){
        int t, w, c; cin >> t >> w >> c;
        if (w == m) w = 0;
        a[t].emplace_back(w, c);
    }
    vector<int>dp(m, oo);
    dp[0] = 0;
    for (int c = 1; c <= k; c++){
        vector<int>new_dp(m, oo);        
        for (auto [rest, cost]: a[c]){
            for (int r = 0, cc = rest; r < m; r++, cc = (cc == m-1 ? 0 : cc+1)){
                new_dp[cc] = min(new_dp[cc], dp[r] + cost);
            }
        }
        dp.swap(new_dp);
    }
    debug(dp);
    auto ans = dp;
    ans[0] = 0;
    set<T>s;
    for (int i = 0; i<m; i++){
        if (dp[i] != oo) {
            s.insert({dp[i], i});
        }
    } 
    while ((int)s.size()){
        auto [d, v] = *s.begin();
        s.erase(s.begin());
        if (ans[v] < d) continue;
        for (int i = 0, cc = v; i<m; i++, cc = (cc == m-1 ? 0 : cc+1)){
            if (ans[cc] > ans[v] + dp[i]){
                ans[cc] = ans[v] + dp[i];
                s.insert({ans[cc], cc});
            }
        }
    }
    // for (int rep = 1; rep < m; rep++){
        //new_dp[i] = min(prevdp[k]+dp[j]) k+j=i
        // vector<int>new_dp(m, oo);
        // for (int i = 0; i<m; i++){
        //     for (int j = 0; j<m; j++){
        //         new_dp[(i+j)%m] = min(new_dp[(i+j)%m], prevdp[i] + dp[j]);
        //     }
        // }
        // for (int i = 0; i<m; i++){
        //     ans[i] = min(ans[i], new_dp[i]);
        // }
    //     prevdp.swap(new_dp);
    // }
    for (auto x: ans) {
        if (x == oo) cout << "-1\n";
        else cout << x << "\n";
    }
}

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

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}