Problem G. Бег
Input file name: running.in
Output file name: running.out
Time limit: 2 s
Memory limit: 256 MB

Чтобы поддерживать себя в хорошей физической форме, студент Вася решил добираться по утрам из общежития в университет бегом. Вася выбирает маршрут пробежки: хочется, чтобы в начале пути нужно было поднапрячься (чтобы сначала дорога шла в гору), а затем во время второй части пути можно было расслабиться (и насладиться лёгким ветерком на спуске).

В маршруте, конечно, могут попадаться горизонтальные участки. Тем не менее, первая часть пути должна включать некоторый подъём и не может содержать спусков (чтобы бегун не расслаблялся), а вторая часть пути, наоборот, обязана включать спуск под уклон и не может предусматривать движения вверх (под конец у нетренированного бегуна сил уже не хватает…). Движение всё время по ровной местности Васю бы не устроило: это скучно.

Используя информацию о рельефе и конфигурации дорожной сети города, в котором живёт Вася, помогите ему выбрать самый короткий маршрут пробежки. По всем дорогам города можно двигаться в любом из двух направлений.

Input

В первой строке записаны целые числа N и M — число перекрёстков (2 ≤ N ≤ 100 000) и число дорог (0 ≤ M ≤ 100 000). Перекрёстки пронумерованы целыми числами от 1 до N. Общежитие находится возле перекрёстка 1, здание университета — возле перекрёстка N. Во второй строке записано N чисел hi — высоты расположения перекрёстков. Высота задаётся в метрах над уровнем моря целым числом в промежутке от −10 994 (глубина Марианского жёлоба) до 8 848 (высота горы Джомолунгма) включительно. В последующих M строках описываются дороги. Каждая дорога задаётся двумя числами ui и vi — номерами перекрёстков, которые она соединяет (1 ≤ ui ≠ vi ≤ N), — и числом di — длиной в метрах (1 ≤ di ≤ 10 000). Гарантируется, что между любой парой перекрёстков может быть не более одной дороги. Высота местности при движении вдоль любой дороги изменяется монотонно (возрастает, убывает или остаётся постоянной в зависимости от высот концевых перекрёстков).

Output

Выведите одно число — длину кратчайшего маршрута из общежития в университет, который удовлетворяет требованиям Васи. Если такого маршрута нет, выведите −1.

Examples


running.in running.out
4 5
100 100 101 99
1 2 3
2 3 5
3 4 7
1 4 14
2 4 10
15
3 2
100 99 100
1 2 1
2 3 1
-1