Алгоритм Дейкстри

Home by trains

One of the teams participating in the Olympic Games has decided to return home by trains. The guys wanted to get home as soon as possible. Unfortunately, not all the trains come from the Olympic city to the station, where the boys live. And what's even more insulting, not all the trains passing through the stations, stop at them (in general, the train does not stop at all the stations which passes).

The stations in a line are numbered with integers from 1 to n. The station number 1 is located in the city, home of the Olympics, and at time 0, guys come to the station. The station where the guys want to get has the number e.

Write a program that by the schedule of the trains calculates the minimum time the guys can get home.

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.


Initially the numbers n (2n100) and e (2en) are given. Next number m (0m100) denotes the number of train routes. Then the description of m routes is given. The description of each route starts with the number ki (2kin) - the number of stations where it stops, and then ki pairs of numbers, the first one gives the station number, and the second one gives the time when the train stops here (the time is an integer from the interval from 0 to 109). The stations of one route are sorted in ascending order of time. In one route the train always moves in one direction - either from the Olympic city or to the Olympic city.


Print one number - the minimum time in which the children can achieve their station. If its impossible to go home using the existed number of routes, print -1.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 3
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
Output example #1
Input example #5
10 2
6 10 10 9 14 8 15 6 20 5 21 2 30
4 1 0 4 10 7 15 9 20
4 3 9 4 11 7 13 9 14
Output example #5