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
line1 = input()
line1 = list(map(int, line1.split(" ")))
n, k, m = line1

from collections import defaultdict, deque


zelki_po_kolorze = defaultdict(lambda: {})

for i in range(n):
    line3 = input()
    line3 = list(map(int, line3.split(" ")))
    kolor, masa, cena = line3
    if masa % m not in zelki_po_kolorze[kolor]:
        zelki_po_kolorze[kolor][masa] = cena
    elif zelki_po_kolorze[kolor][masa % m] > cena:
        zelki_po_kolorze[kolor][masa % m] = cena



if len(zelki_po_kolorze.keys()) < k:
    print("\n".join(map(str, [0] + [-1] * (m - 1))))
else:

    new_zelki = [list(z.items()) for z in list(zelki_po_kolorze.values())]

    ciagi = []
    import itertools

    ciagi_mk = []

    minimum_costs = [float("inf")] * m

    for ciag in itertools.product(*new_zelki):
        ciag_koszt = sum([p[1] for p in ciag])
        ciag_masa = sum([p[0] for p in ciag]) % m
        ciagi_mk.append([ciag_koszt, ciag_masa])


    states = deque(ciagi_mk.copy())
    new_states = deque([])

    for cc, cm in states:
        if minimum_costs[cm] > cc:
            minimum_costs[cm] = cc
    minimum_costs[0] = 0

    states = deque([s for s in states if minimum_costs[s[1]] == s[0]])
    ciagi_mk = list(states).copy()

    minimum_costs = [float("inf")] * m
    minimum_costs[0] = 0

    while states:
        current_state = states.popleft()
        cc, cm = current_state

        if minimum_costs[cm] > cc:
            minimum_costs[cm] = cc
        else:
            continue

        for ac, am in ciagi_mk:
            states.append(
                [cc + ac, (cm + am) % m])

    ans = [0] + minimum_costs[1:]
    ans = [n if n != float("inf") else -1 for n in ans]
    print("\n".join(map(str, ans)))