Bajtazar，重金屬樂團 Algosia in Antichains 的主唱，正在為他在 Bajtoszyce 的演唱會做準備。除了準備觀眾喜愛的歌曲外，準備音響設備也同樣重要。

音響系統由 $n$ 個路由器和 $m$ 個放大器組成。麥克風連接到路由器 1，揚聲器連接到路由器 $n$。每個放大器連接兩個路由器（輸入端和輸出端），並具有一個增益係數 $w_i$。每個路由器也有一個最大頻寬 $p_i$。

麥克風的訊號功率為 1。Bajtazar 可以配置系統，透過由放大器連接的任意路由器序列來傳輸訊號。訊號經過放大器後，其功率會乘以該放大器的增益係數。如果在任何時刻，當前傳輸訊號的功率超過了訊號所經過路由器的頻寬，該路由器就會燒毀，這是 Bajtazar 絕對想要避免的。

訊號可以多次經過同一個路由器或放大器。Bajtazar 希望將訊號傳輸到揚聲器，在不超過任何路由器頻寬的前提下，達到最大可能的增益。請幫助他達成目標。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 100$)，表示 Bajtazar 擁有的音響系統數量。接下來是 $T$ 個音響系統的描述。

每個描述的第一行包含兩個整數 $n$ 和 $m$ ($1 \le n, m$)，表示路由器的數量和放大器的數量。

下一行包含 $n$ 個整數 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$)，表示各個路由器的頻寬。

接下來的 $m$ 行包含放大器的描述，其中第 $i$ 個放大器由三個整數 $a_i, b_i$ 和 $w_i$ ($1 \le a_i, b_i \le n, 1 \le w_i \le 10^9$) 組成，分別表示第 $i$ 個放大器的輸入路由器、輸出路由器以及增益係數。

所有測試案例中 $n$ 的總和不超過 100，$m$ 的總和不超過 200。

輸出格式

輸出 $T$ 行；第 $i$ 行應包含一個整數，表示第 $i$ 個音響系統中訊號可能達到的最大增益。如果無法使用第 $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$)

在第二個系統中，最佳解為： $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$)

在第三個系統中： $1 \to 1$ (功率為 2) $\to 1$ (功率為 $2 \cdot 2 = 4$) $\to 2$ (功率為 $4 \cdot 1 = 4$)

在第四個系統中，使用放大器傳輸訊號會導致功率達到 $1\,000\,000\,000$，超過了路由器 2 的頻寬。因此，無法以任何功率傳輸訊號。