Бальтазар, вокалист хеви-метал группы Algosia in Antichains, готовится к концерту в Бальтошицах. Помимо подготовки любимых песен фанатов, собравшихся в зале, не менее важно подготовить звуковое оборудование.

Звуковая система состоит из $n$ маршрутизаторов и $m$ усилителей. Микрофон подключен к маршрутизатору номер 1, а динамик — к маршрутизатору $n$. Каждый усилитель соединяет два маршрутизатора (входной и выходной) и имеет коэффициент усиления $w_i$. Каждый маршрутизатор также имеет максимальную пропускную способность $p_i$.

Мощность сигнала от микрофона равна 1. Бальтазар может настроить систему так, чтобы передавать сигнал от микрофона через любую последовательность маршрутизаторов, соединенных усилителями. Мощность сигнала после прохождения через усилитель умножается на коэффициент усиления этого усилителя. Если в любой момент мощность передаваемого сигнала превысит пропускную способность маршрутизатора, через который он проходит, этот маршрутизатор сгорит, чего Бальтазар категорически хочет избежать.

Сигнал может проходить через один и тот же маршрутизатор или усилитель любое количество раз. Бальтазар хочет передать сигнал к динамику, достигнув максимально возможного усиления, не превышая при этом пропускную способность ни одного из маршрутизаторов. Помогите ему в этом.

Входные данные

В первой строке содержится одно целое число $T$ ($1 \le T \le 100$), обозначающее количество звуковых систем, имеющихся у Бальтазара. Далее следуют описания $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

Пример 2

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. Следовательно, передача сигнала любой мощности невозможна.