B. Планеты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гоа'улд Апофис снова захватил команду Джека О'Нила! Сам Джек смог спастись, но к тому времени корабль Апофиса уже совершил прыжок в гиперпространство. Однако Джек знает, на какой планете высадится Апофис. Чтобы спасти друзей, Джеку предстоит несколько раз пройти через звездные врата, чтобы попасть на эту планету.

Всего в галактике находится n планет, пронумерованных числами от 1 до n. Джек находится на планете с номером 1, а Апофис высадится на планете с номером n. Между некоторыми парами планет можно перемещаться через звездные врата (перемещение возможно в обоих направлениях); перемещение занимает положительное и, возможно, для разных пар планет неодинаковое количество секунд. Джек начинает свое путешествие в момент времени 0.

Может оказаться, что на планету, где сейчас находится Джек, через звездные врата прибывают другие путешественники, в этом случае Джек должен подождать ровно 1 секунду, прежде чем сам сможет воспользоваться звездными вратами. То есть, если в момент времени t на планету прибывает другой путешественник, то Джек может пройти через врата только в момент времени t + 1, если только в момент времени t + 1 на ту же планету не прибывают еще путешественники.

Зная информацию о времени перемещения между планетами, а также о моментах времени, когда Джек не сможет пользоваться звездными вратами на конкретных планетах, определите наименьшее время, за которое он сможет попасть на планету с номером n.

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

Первая строка содержит два целых числа, разделенные пробелом: n (2 ≤ n ≤ 105), количество планет в галактике, и m (0 ≤ m ≤ 105), количество пар планет, между которыми можно перемещаться сквозь звездные врата. Далее следуют m строк, в каждой из них содержится три целых числа: i-ая строка содержит номера планет ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), между которыми есть связь через звездные врата, и целочисленное время (в секундах) перемещения между этими планетами ci (1 ≤ ci ≤ 104). Гарантируется, что между любой парой планет существует не более одного перехода, образованного звездными вратами.

Далее следуют n строк: i-тая строка содержит целое число ki (0 ≤ ki ≤ 105), которое обозначает количество моментов времени, в которые на планету с номером i прибывают другие путешественники. Далее через пробел следуют ki упорядоченных по возрастанию различных целых чисел tij (0 ≤ tij < 109). Число tij обозначает, что в момент времени tij (в секундах) на планету i прибывает другой путешественник. Гарантируется, что сумма всех ki не превышает 105.

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

Выведите единственное число — наименьшее количество времени, которое понадобится Джеку, чтобы попасть с планеты 1 на планету n. Если Джек не сможет попасть на планету n ни за какое время, выведите число -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
Входные данные
3 1
1 2 3
0
1 3
0
Выходные данные
-1
Примечание

В первом примере у Джека три выбора, куда переместиться с планеты 1. Если он переместится сразу на планету 4, то потратит 8 секунд. Если он переместится на планету 3, то потратит 3 секунды, но, поскольку в моменты времени 3 и 4 на планету 3 прибывают другие путешественники, то он сможет отправиться на планету 4 только в момент времени 5, затратив в сумме 8 секунд. Если же Джек переместится на планету 2, а потом на планету 4, то потратит в сумме всего лишь 2 + 5 = 7 секунд.

Во втором примере с планеты 1 на планету 3 нельзя попасть, перемещаясь через звездные врата.