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.