Поиск

Турист


Ограничение времени - 1 секунда

Ввод - input.txt

Ограничение памяти - 16Mb

Вывод - output.txt

В городе Х всего одна улица и n остановок, которые пронумерованы в порядке следования вдоль улицы. Мэр города решил оптимизировать транспортную систему. Для этого он запретил промежуточные остановки автобусов — теперь у каждого автобуса две остановки: начальная и конечная.

Турист хочет добраться с первой остановки до n-той на автобусах, возможно, с пересадками. Он узнал, что существует m маршрутов автобусов. Для каждого из них известна начальная остановка ai, конечная остановка bi и стоимость проезда ci.

Все автобусы следуют только по направлению «из ai в bi» (но не обратно), причем для всех маршрутов верно, что ai<bi.

Помогите ему найти самый дешевый способ добраться, или определите, что искомого маршрута не существует.


Формат ввода

На первой строке через пробел вводятся два натуральных числа n и m — число остановок и маршрутов автобусов соответственно (2 ≤ n ≤ 1018, 1 ≤ m ≤ 105).

В каждой из следующих m строк вводится тройка натуральных чисел ai, bi и ci (1 ≤ ai < bi ≤ n, 1 ≤ ci ≤ 109).


Формат вывода

Если искомого маршрута не существует, выведите одно число -1.

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

Автобусные маршруты нумеруются с единицы в порядке следования во входных данных.

Пример 1

Ввод

3 3

1 2 5

1 3 10

2 3 1

Вывод

6

1 3

Пример 2

Ввод

3 1

1 2 5

Вывод

-1

Для отправки решения задачи необходимо авторизоваться!