В некоторой местности имеется $$$n$$$ городов. Некоторые пары городов соединены двухсторонними дорогами. Любые два города соединены напрямую не более чем одной дорогой.
Студент Василий хочет доехать на своём автомобиле от города 1 до города $$$n$$$. Он заранее рассчитал для каждой дороги, сколько литров бензина нужно, чтобы проехать по этой дороге на его машине.
Заправочные станции имеются только в городах. Однако, Василий может захватить с собой сколь угодно много канистр, поэтому в любом городе он может заправить любое количество бензина. Изначально он находится на заправке в первом городе, и у него имеется ноль литров бензина.
Цена за литр бензина в разных городах может быть разной. Определите, какую наименьшую сумму денег должен потратить Василий, чтобы добраться из города 1 в город $$$n$$$. Также определите его маршрут движения и сколько литров бензина он должен купить в каждом городе по пути.
В первой строке входных данных записаны два целых числа $$$n$$$ и $$$m$$$ — количество городов и количество дорог ($$$2 \le n \le 1000$$$, $$$0 \le m \le 10000$$$).
В следующей строке записаны $$$n$$$ целых чисел $$$c_i$$$ — стоимость литра бензина в каждом городе ($$$1 \le c_i \le 100$$$).
В следующих $$$m$$$ строках записана информация о дорогах — тройки целых чисел $$$u_i$$$, $$$v_i$$$ и $$$f_i$$$, где $$$u_i$$$ и $$$v_i$$$ — города, которые соединяет очередная дорога ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), $$$f_i$$$ — количество бензина, требуемое для проезда по этой дороге ($$$1 \le f_i \le 100$$$).
Если от города 1 можно доехать до города $$$n$$$, то в первой строке выведите целое число — минимальную сумму, которую придётся потратить на покупку бензина. Во второй строке выведите целое число $$$k$$$ — количество городов в найденном маршруте. В следующих $$$k$$$ строках выведите пары целых чисел — номер очередного города в порядке следования и количество литров бензина, которое в этом городе нужно купить. Если есть несколько верных ответов, выведите любой.
Если от города 1 нельзя доехать до города $$$n$$$, то выведите -1.
5 550 40 10 100 751 2 41 4 32 5 93 4 54 5 10
550 5 1 8 4 0 3 15 4 0 5 0
4 210 20 30 401 2 503 4 100
-1
Рисунок к первому примеру:
Рядом с вершинами подписаны стоимости бензина, рядом с рёбрами — расход в литрах. В примере мы заправляем 8 литров в городе 1, едем в город 4, далее заезжаем в город 3 за дешёвым бензином и заправляем там 15 литров, возвращаемся в город 4 и едем в город 5.
