ヘヴィメタルバンド「Algosia in Antichains」のボーカルであるBajtazarは、Bajtoszyceでのコンサートに向けて準備を進めています。観客のために好きな曲を準備することに加え、音響機材の準備も同様に重要です。

音響システムは $n$ 個のルーターと $m$ 個のアンプで構成されています。マイクはルーター1に接続されており、スピーカーはルーター $n$ に接続されています。各アンプは2つのルーター（入力ルーターと出力ルーター）を接続し、増幅率 $w_i$ を持っています。また、各ルーターには最大帯域幅 $p_i$ が設定されています。

マイクからの信号の強度は1です。Bajtazarは、アンプで接続されたルーターの任意の経路を通るようにシステムを設定できます。信号がアンプを通過すると、その強度はアンプの増幅率倍になります。信号の強度が通過するルーターの帯域幅を一度でも超えると、そのルーターは焼き切れてしまいます。Bajtazarはこれを絶対に避けなければなりません。

信号は同じルーターやアンプを何度でも通過できます。Bajtazarは、どのルーターの帯域幅も超えることなく、最終的にスピーカーへ信号を送り、可能な限り最大の増幅率を得たいと考えています。これを達成する手助けをしてください。

入力

最初の行には、Bajtazarが所有する音響システムの数を示す整数 $T$ ($1 \le T \le 100$) が含まれます。続いて、$T$ 個の音響システムの記述が続きます。

各システムの記述の最初の行には、ルーターの数とアンプの数を示す2つの整数 $n$ と $m$ ($1 \le n, m$) が含まれます。

次の行には、各ルーターの帯域幅を示す $n$ 個の整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$) が含まれます。

続く $m$ 行にはアンプの記述があり、各行は3つの整数 $a_i, b_i, w_i$ ($1 \le a_i, b_i \le n, 1 \le w_i \le 10^9$) で構成され、それぞれ入力ルーター、出力ルーター、およびそのアンプの増幅率を表します。

すべてのシステムにおける $n$ の合計は100を超えず、$m$ の合計は200を超えません。

出力

$T$ 行を出力してください。$i$ 行目には、$i$ 番目の音響システムにおける信号の最大増幅率を示す整数を1つ出力します。もし $i$ 番目のシステムでスピーカーまで信号を送ることが不可能な場合は、代わりに $-1$ を出力してください。

入出力例

入力 1

4
2 3
250 1000
1 1 2
1 2 3
2 1 37
3 5
500 800 1100
1 1 2
1 2 1
2 2 3
2 3 1
3 3 5
2 2
4 4
1 1 2
1 2 1
2 1
10 10
1 2 1000000000

出力 1

666
1080
4
-1

注記

例の解説：最初の音響システムにおいて、最適な設定で信号を以下のように送ります：

$1 \to 1$ (強度2の信号) $\to 2$ (強度 $2 \cdot 3 = 6$ の信号) $\to 1$ (強度 $6 \cdot 37 = 222$ の信号) $\to 2$ (強度 $222 \cdot 3 = 666$ の信号)

2番目のシステムにおける最適な解は以下の通りです：

$1 \to 1$ (強度2の信号) $\to 1$ (強度 $2 \cdot 2 = 4$ の信号) $\to 1$ (強度 $4 \cdot 2 = 8$ の信号) $\to 2$ (強度 $8 \cdot 1 = 8$ の信号) $\to 2$ (強度 $8 \cdot 3 = 24$ の信号) $\to 2$ (強度 $24 \cdot 3 = 72$ の信号) $\to 2$ (強度 $72 \cdot 3 = 216$ の信号) $\to 3$ (強度 $216 \cdot 1 = 216$ の信号) $\to 3$ (強度 $216 \cdot 5 = 1080$ の信号)

3番目のシステム：

$1 \to 1$ (強度2の信号) $\to 1$ (強度 $2 \cdot 2 = 4$ の信号) $\to 2$ (強度 $4 \cdot 1 = 4$ の信号)

4番目のシステムでは、アンプで信号を送ると強度が $1\,000\,000\,000$ となり、ルーター2の帯域幅を超えてしまいます。そのため、どのような強度の信号を送ることも不可能です。