Гоа'улд Апофис снова захватил команду Джека О'Нила! Сам Джек смог спастись, но к тому времени корабль Апофиса уже совершил прыжок в гиперпространство. Однако Джек знает, на какой планете высадится Апофис. Чтобы спасти друзей, Джеку предстоит несколько раз пройти через звездные врата, чтобы попасть на эту планету.
Всего в галактике находится n планет, пронумерованных числами от 1 до n. Джек находится на планете с номером 1, а Апофис высадится на планете с номером n. Между некоторыми парами планет можно перемещаться через звездные врата (перемещение возможно в обоих направлениях); перемещение занимает положительное и, возможно, для разных пар планет неодинаковое количество секунд. Джек начинает свое путешествие в момент времени 0.
Может оказаться, что на планету, где сейчас находится Джек, через звездные врата прибывают другие путешественники, в этом случае Джек должен подождать ровно 1 секунду, прежде чем сам сможет воспользоваться звездными вратами. То есть, если в момент времени t на планету прибывает другой путешественник, то Джек может пройти через врата только в момент времени t + 1, если только в момент времени t + 1 на ту же планету не прибывают еще путешественники.
Зная информацию о времени перемещения между планетами, а также о моментах времени, когда Джек не сможет пользоваться звездными вратами на конкретных планетах, определите наименьшее время, за которое он сможет попасть на планету с номером n.
Выходные данные
Выведите единственное число — наименьшее количество времени, которое понадобится Джеку, чтобы попасть с планеты 1 на планету n. Если Джек не сможет попасть на планету n ни за какое время, выведите число -1.
Примечание
В первом примере у Джека три выбора, куда переместиться с планеты 1. Если он переместится сразу на планету 4, то потратит 8 секунд. Если он переместится на планету 3, то потратит 3 секунды, но, поскольку в моменты времени 3 и 4 на планету 3 прибывают другие путешественники, то он сможет отправиться на планету 4 только в момент времени 5, затратив в сумме 8 секунд. Если же Джек переместится на планету 2, а потом на планету 4, то потратит в сумме всего лишь 2 + 5 = 7 секунд.
Во втором примере с планеты 1 на планету 3 нельзя попасть, перемещаясь через звездные врата.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
|
7
|
|
2
|
3 1
1 2 3
0
1 3
0
|
-1
|