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
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>> zel [7007];

vector<long long> dp [7007];
vector<int> in [7007];
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int N,K,M;cin>>N>>K>>M;
    for(int i=0;i<N;i++)
    {
        int k,m;
        long long v;
        cin>>k>>m>>v;
        if(m==M) m=0;
        zel[k].push_back({m,v});
    }
    for(int i=1;i<=K;i++)
    {
        dp[i].resize(M,-1);
    }
    for(int i=0;i<zel[1].size();i++)
    {
        if(dp[1][zel[1][i].first]== -1 || dp[1][zel[1][i].first] > zel[1][i].second)
        {
            dp[1][zel[1][i].first]=zel[1][i].second;
            in[1].push_back(zel[1][i].first);
        }
    }

    for(int rzad=2;rzad<=K;rzad++)
    {
        for(int i=0;i<zel[rzad].size();i++)
        {
            int masa=zel[rzad][i].first;

            for(int j=0;j<in[rzad-1].size();j++)
            {
                int up = (in[rzad-1][j]+ zel[rzad][i].first )%M; 
                if( dp[rzad][up]== -1 || dp[rzad][up] > dp[rzad-1][in[rzad-1][j]] + zel[rzad][i].second)
                {
                    dp[rzad][up]= dp[rzad-1][in[rzad-1][j]] + zel[rzad][i].second;
                    in[rzad].push_back(up);
                }
            }
        }
    }


    queue<int>updated;
    vector<long long>tab(M,0);
    for(int i=1;i<M;i++)
    {
        tab[i]=dp[K][i];
    } 

    for(int i=0;i<in[K].size();i++)
    {
        for(int j=0;j<in[K].size();j++)
        {
            int up = (in[K][i] + in[K][j]) % M;
            if( tab[up]==-1)
            {
                in[K].push_back(up);
                tab[up]= tab[in[K][i]]+tab[in[K][j]];
                updated.push(up);
            } 
            else if (tab[up]> tab[in[K][i]]+tab[in[K][j]])
            {
                tab[up]=tab[in[K][i]]+tab[in[K][j]];
                updated.push(up);
            }
        }
    }

    while(!updated.empty())
    {
        int now= updated.front();
        updated.pop();
        for(int i=0;i<in[K].size();i++)
        {
            int up = (now+in[K][i])%M;
            if(tab[up]==-1)
            {
                in[K].push_back(up);
                tab[up]=tab[in[K][i]]+tab[now];
            }
            else if(tab[up]>tab[in[K][i]]+tab[now])
            {
                tab[up]=tab[in[K][i]]+tab[now];
                updated.push(up);
            }
        }
    }
    for(int i=0;i<M;i++)
    cout<<tab[i]<<endl;
}