추측

$N$장의 카드가 모두 뒷면이 위로 오도록 한 줄로 놓여 있다. 각 카드에는 $m$ 이하의 양의 정수가 하나씩 적혀 있다.

$i$번째 카드에 적힌 정수를 $A_i$라고 하자.

목표는 $A_1, A_2, \cdots, A_N$을 모두 맞히는 것이다.

할 수 있는 연산은 다음 하나뿐이다.

• $i$번째 카드를 골라 뒤집어 적힌 정수를 확인한다. 이때 비용은 $X_i$이다.

또한 다음 정보가 주어진다.

• 각 $i = 1, 2, \cdots, M$에 대하여 $A_{a_i} + A_{b_i} \equiv c_i \pmod m$.

$A_1, A_2, \cdots, A_N$을 모두 맞히는 데 필요한 최소 비용은 얼마인가?

첫째 줄에 $N$, $M$, $m$이 공백으로 구분되어 주어진다.

둘째 줄에 $X_1, X_2, \cdots, X_N$이 공백으로 구분되어 주어진다.

이어서 $M$개의 줄이 주어지고, $i$번째 줄에 $a_i$, $b_i$, $c_i$가 공백으로 구분되어 주어진다.

비용을 얼마나 지불해도 $N$장의 카드에 적힌 정수를 결정할 수 없다면(즉, 주어진 정보에 모순이 있다면) -1만 출력한다.

그렇지 않으면 첫째 줄에 $A_1, A_2, \cdots, A_N$을 모두 맞히는 데 필요한 최소 비용을 출력한다.

둘째 줄에 $A_1, A_2, \cdots, A_N$의 가능한 값 하나인 $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$)
• 입력으로 주어지는 모든 값은 정수이다.