D. Меньше батареек
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В 2077 году, когда роботы захватили мир, они решили посоревноваться в следующей игре.

Есть $$$n$$$ контрольных точек, причем в $$$i$$$-й из них находится $$$b_i$$$ батареек. Изначально Робот находится в $$$1$$$-й точке без батареек и должен добраться до $$$n$$$-й.

Всего есть $$$m$$$ однонаправленных проходов между точками. $$$i$$$-й из них позволяет переместиться от точки $$$s_i$$$ в точку $$$t_i$$$ ($$$s_i \lt t_i$$$), но не наоборот. Причем пройти по $$$i$$$-му проходу можно только если у робота есть хотя бы $$$w_i$$$ заряженных батареек, иначе он разрядится по пути.

Когда робот оказывается в точке $$$v$$$, он может дополнительно взять любое количество батареек от $$$0$$$ до $$$b_v$$$ включительно. А также он всегда носит все ранее подобранные батарейки, а в каждой контрольной точке он заряжает все ранее подобранные батарейки.

Найдите минимальное количество батареек, которое может быть у робота в конце пути, или сообщите, что добраться от первой точки до последней невозможно.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n, m$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 3 \cdot 10^5$$$) — количество контрольных точек и количество проходов соответственно.

Во второй строке даны $$$n$$$ чисел $$$b_i$$$ ($$$0 \leq b_i \leq 10^9$$$) — количество батареек в $$$i$$$-й контрольной точке.

Следующие $$$m$$$ строк содержат по три целых числа $$$s_i, t_i, w_i$$$ ($$$1 \leq s_i \lt t_i \leq n, 1 \leq w_i \leq 10^9$$$) — конечные точки прохода и минимальное количество батареек, необходимое для прохода по нему.

Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что сумма $$$m$$$ не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимальное количество батареек, которое может оказаться у вас в конце пути, или $$$-1$$$, если добраться до точки $$$n$$$ невозможно.

Пример
Входные данные
4
3 3
2 0 0
1 2 1
2 3 1
1 3 2
5 6
2 2 5 0 1
1 2 2
1 3 1
1 4 3
3 5 5
2 4 4
4 5 3
2 0
1 1
4 4
3 10 0 0
1 2 1
1 3 3
2 3 10
3 4 5
Выходные данные
1
4
-1
10
Примечание

В первом наборе входных данных нужно взять $$$1$$$ батарейку в стартовой точке, затем перейти в точку $$$2$$$, а затем в $$$3$$$.

Во втором наборе входных данных нужно взять $$$2$$$ батарейки в стартовой точке, затем перейти в точку $$$2$$$, взять еще $$$2$$$ батарейки, пройти в точку $$$4$$$, а затем в точку $$$5$$$.

В третьем наборе входных данных пути из точки $$$1$$$ в точку $$$n$$$ не существует.

В четвертом наборе входных данных нужно взять $$$1$$$ батарейку в стартовой точке, затем перейти в точку $$$2$$$, взять $$$9$$$ батареек, перейти в точку $$$3$$$, а затем в точку $$$4$$$.