Турист

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

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

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

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

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

В первой строке входного файла INPUT.TXT записаны через пробел два натуральных числа n и m - число остановок и маршрутов автобусов соответственно (1 ≤ n ≤ 10¹⁸, 1 ≤ m ≤ 10⁵).

В каждой из следующих m строк вводится тройка натуральных чисел a_i , b_i и c_i (1 ≤ a_i < b_i ≤ n, 1 ≤ c_i ≤ 10⁹).

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

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

Если маршрут существует, в первой строке выходного файла OUTPUT.TXT выведите одно число – минимальную сумму, которую необходимо потратить на проезд. Во второй строке через пробел перечислите номера маршрутов, которыми должен воспользоваться турист, в порядке использования. Если вариантов ответа несколько, выведите любой. Автобусные маршруты нумеруются с единицы в порядке следования во входных данных.

Примеры

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

[Обсуждение] [Все попытки] [Лучшие попытки]