시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB4210922.500%

문제

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.

예제 입력 1

5 2 7
1 2 1 3 3
1 3 6
4 5 0

예제 출력 1

6
5 2 1 3 4

You can do the operation on the first, second, and fifth cards to guess all of $A_i$ correctly. The minimum cost you have to pay is $6$.

예제 입력 2

2 2 3
3 5
1 2 0
1 2 1

예제 출력 2

-1

$A_1 + A_2 \equiv 0$ and $A_1 + A_2 \equiv 1$ can't be satisfied at the same time.

출처