Guessing

There are $N$ cards in a row, all face down. Each card has a positive integer at most $m$ written on it.

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 perform is:

• Choose the $i$-th card and flip it to check the integer written on it. This costs $X_i$.

You are also 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 needed 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$.

The following $M$ lines describe the information. The $i$-th line contains three integers $a_i$, $b_i$, and $c_i$.

If the integers on the $N$ cards cannot be determined no matter how much you pay (that is, if the given information is contradictory), print only -1.

Otherwise, print the minimum cost needed to guess all $A_i$ correctly on the first line.

On the second line, print $N$ integers $A'_1, A'_2, \cdots, A'_N$, one possible assignment for $A_1, A_2, \cdots, A_N$, separated by spaces.

• $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 the input are integers.