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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll n,k,m;
    cin>>n>>k>>m;
    vector<vector<pair<ll,ll>>>a(k);
    for(ll i=0;i<n;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        a[x-1].push_back({y,z});
    }
    bool p=false;
    for(ll i=0;i<k;i++)
    {
        if(a[i].size()==0)
        {
            p=true;
            break;
        }
    }
    if(p)
    {
        cout<<0<<endl;
        for(ll i=1;i<m;i++)
        {
            cout<<-1<<endl;
        }
        return 0;
    }
    vector<vector<ll>>b(k,vector<ll>(m,-1));
    for(ll i=0;i<a[0].size();i++)
    {
        if(b[0][a[0][i].st%m]>a[0][i].nd or b[0][a[0][i].st%m]==-1)
        {
            b[0][a[0][i].st%m]=a[0][i].nd;
        }
    }
    for(ll i=1;i<k;i++)
    {
        for(ll j=0;j<m;j++)
        {
            if(b[i-1][j]>-1)
            {
                for(ll o=0;o<a[i].size();o++)
                {
                    if(b[i][(j+a[i][o].st)%m]>(b[i-1][j]+a[i][o].nd) or b[i][(j+a[i][o].st)%m]==-1)
                    {
                        b[i][(j+a[i][o].st)%m]=(b[i-1][j]+a[i][o].nd);
                    }
                }
            }
        }
    }

    vector<ll>c(m,-1);
    c[0]=0;
    for(ll i=0;i<m;i++)
    {
        if(b[k-1][i]>-1)
        {
            ll e=i;
            for(ll j=1;j<m+2;j++)
            {
                if((e*j)%m==e && j>1)
                {
                    break;
                }
                if(c[(e*j)%m]>j*b[k-1][i] or c[(e*j)%m]==-1)
                {
                    c[(e*j)%m]=j*b[k-1][i];
                }
            }
        }
    }
    vector<pair<ll,ll>>d;
    for(ll i=0;i<m;i++)
    {
        if(c[i]>-1)
        {
            d.push_back({i,c[i]});
        }
    }
    vector<vector<ll>>e(d.size()+1,vector<ll>(m,-1));
    e[0][0]=0;
    for(ll i=1;i<e.size();i++)
    {
        e[i]=e[i-1];
        for(ll j=0;j<m;j++)
        {
            if(e[i-1][j]>-1 &&(e[i][(j+d[i-1].st)%m]>(e[i-1][j]+d[i-1].nd) or e[i][(j+d[i-1].st)%m]==-1))
            {
                e[i][(j+d[i-1].st)%m]=(e[i-1][j]+d[i-1].nd);
            }
        }
    }
    for(ll i=0;i<m;i++)
    {
        cout<<e[e.size()-1][i]<<endl;
    }
}