CF2115B.Gellyfish and Camellia Japonica

Gellyfish has an array of $n$ integers $c_1, c_2, \ldots, c_n$. In the beginning, $c = [a_1, a_2, \ldots, a_n]$.

Gellyfish will make $q$ modifications to $c$.

For $i = 1,2,\ldots,q$, Gellyfish is given three integers $x_i$, $y_i$, and $z_i$ between $1$ and $n$. Then Gellyfish will set $c_{z_i} := \min(c_{x_i}, c_{y_i})$.

After the $q$ modifications, $c = [b_1, b_2, \ldots, b_n]$.

Now Flower knows the value of $b$ and the value of the integers $x_i$, $y_i$, and $z_i$ for all $1 \leq i \leq q$, but she doesn't know the value of $a$.

Flower wants to find any possible value of the array $a$ or report that no such $a$ exists.

If there are multiple possible values of the array $a$, you may output any of them.

Gellyfish 有一个长度为 $n$ 的整数数组 $c_1, c_2, \ldots, c_n$。初始时，$c = [a_1, a_2, \ldots, a_n]$。

Gellyfish 将对 $c$ 进行 $q$ 次修改。

对于 $i = 1,2,\ldots,q$，Gellyfish 会得到三个介于 $1$ 到 $n$ 之间的整数 $x_i$、$y_i$ 和 $z_i$，然后执行赋值操作：$c_{z_i} := \min(c_{x_i}, c_{y_i})$。

经过这 $q$ 次修改后，$c = [b_1, b_2, \ldots, b_n]$。

现在 Flower 知道了最终数组 $b$ 的值，以及所有 $1 \leq i \leq q$ 对应的 $x_i$、$y_i$ 和 $z_i$ 的值，但她不知道初始数组 $a$ 的值。

Flower 希望找出任意一个可能的初始数组 $a$，或者判断不存在这样的 $a$。

如果存在多个可能的 $a$，你可以输出其中任意一个。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \leq n, q \leq 3 \cdot 10^5$) — the size of the array and the number of modifications.

The second line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$) — the value of the array $c$ after the $q$ modifications.

The following $q$ lines each contain three integers $x_i$, $y_i$, and $z_i$ ($1 \leq x_i, y_i, z_i \leq n$) — describing the $i$-th modification.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases does not exceed $3 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 3 \cdot 10^5$）——分别表示数组的大小和修改操作的次数。

每个测试用例的第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$）——表示经过 $q$ 次修改后数组 $c$ 的值。

接下来的 $q$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $z_i$（$1 \leq x_i, y_i, z_i \leq n$）——描述第 $i$ 次修改。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $3 \cdot 10^5$。

For each test case, if $a$ exists, output $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) in a single line. Otherwise, output "-1" in a single line.

If there are multiple solutions, print any of them.

对于每个测试用例，如果存在满足条件的 $a$，则在一行中输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$（其中 $0 \leq a_i \leq 10^9$）；否则，在一行中输出 “-1”。

如果有多个解，输出任意一个即可。

In the first test case, based on the given sequence of modifications, we know that $b_1 = a_1$ and $b_2 = \min(a_1, a_2)$. Therefore, it is necessary that $b_2 \leq b_1$. However, for the given $b$, we have $b_1 \lt b_2$. Therefore, there is no solution.

In the second test case, we can see that the given $c$ becomes $b$ from $a$ after the given modifications, and $c$ is not changed at each modification.

在第一个测试用例中，根据给定的修改序列，我们知道 $b_1 = a_1$ 且 $b_2 = \min(a_1, a_2)$。因此，必须满足 $b_2 \leq b_1$。然而，对于给定的 $b$，有 $b_1 \lt b_2$。因此，无解。

在第二个测试用例中，我们可以看出，给定的 $c$ 在经过所描述的修改后，恰好变为 $b$（即由 $a$ 变为 $b$），且 $c$ 在每次修改中均保持不变。