24063번 - Guessing 스페셜 저지다국어

문제

There are $N$ cards placed face down in a row. A positive integer less than or equal to $m$ is written on each card.

Let $A_i$ be the integer written on the $i$-th card.

Your goal is to guess $A_1, ,円 A_2, ,円 \cdots , ,円 A_N$ correctly.

The only operation you can do is:

• choose the $i$-th card and flip it to check the integer written on it. The cost of doing this is $X_i$.

Also, you are given the following information:

• for each $i = 1, ,円 2, ,円 \cdots , ,円 M,ドル $A_{a_i} + A_{b_i} \equiv c_i \pmod m$.

What is the minimum cost you need to pay to guess all of $A_1, ,円 A_2, ,円 \cdots , ,円 A_N$ correctly?

입력

The first line contains three integers $N,ドル $M$ and $m$.

The second line contains $N$ integers $X_1, ,円 X_2, ,円 \cdots, ,円 X_N$.

This is followed by $M$ lines, the $i$-th line contains three integers $a_i,ドル $b_i$ and $c_i$.

출력

If the $N$ integers written on each card can't be determined no matter how much you pay(i.e. if there's a contradiction in the information), print only -1.

Otherwise, in the first line, print a single integer — the minimum cost you need to pay to guess all of $A_i$ correctly.

In the second line, print $N$ integers $A^\prime_1, ,円 A^\prime_2, ,円 \cdots , ,円 A^\prime_N$ — one of the possibilities of $A_1, ,円 A_2, ,円 \cdots , ,円 A_N$.

제한

• 2ドル \le N \le 2 \times 10^5$
• 1ドル \le M \le 10^6$
• 2ドル \le m \le 10^9$
• 1ドル \le X_i \le 10^4$ (1ドル \le i \le N$)
• 1ドル \le a_i, ,円 b_i \le N$; 0ドル \le c_i < m$ (1ドル \le i \le M$)
• All values in input are integers.

힌트