Space Travel
----- ------

Travel planning in the Slow Galaxy requires a slow
metabolism and a mathematical mind.  A traveler
takes ships going from one star system to another,
but these take many years to make the journey, and
it helps that the inhabitants of this galaxy have
a metabolism a million times slower than ours, and
a lifetime a million times longer.

Still, it pays to make trips optimally.  Ships have
schedules that say when they visit each star system
on their itinerary.  You want to get from one star
system to another by taking a first ship for a while,
then getting off and waiting for another ship to
come and take you further, and so forth, but you want
to get to your ultimate destination as soon as you can.


Input
-----

For each test case, first a line that gives the test
case name.  Then a line of the form

	N M

giving the number of start systems N and number of ships
M.  Then M lines, one per ship, each of the form

    K S1 T1 S2 T1 ... SK TK

where K is the number of stops the ship makes, and Si,
Ti describe the i+1'st stop which is at star system Si
and time Ti.  0 <= T1 < T2 < T3 < ... < TK.

The star systems are numbered 1, 2, ..., N.  You start
at system 1 and your ultimate destination is system N.
Times are integers in years.  If you get to a star
system at time T, you can transfer to any ship arriving
at the star system at time T or later.

	2 <= M <= 10,000
	2 <= K <= 100
	2 <= N <= 10,000
	1 <= Si <= N
	0 <= Ti <= 100,000,000

Input terminates with an end of file.  The test case
name line is at most 80 characters.


Output
------

For each test case, first an exact copy of the test case
name line.  Then a line containing just the earliest
possible time of your arrival at system N assuming that
you start at system 1 at time 0.


Sample Input
------ -----

-- SAMPLE 1 --
6 4
3 1 0 2 10 3 20
4 2 0 4 10 2 20 4 30
4 3 0 5 10 3 20 5 30
6 4 0 5 10 6 20 4 30 5 40 6 50
-- SAMPLE 2 --
10 7
5 1 0 3 10 5 20 7 30 9 40
4 2 20 1 40 2 60 1 80
10 5 30 4 40 3 50 4 60 5 70 6 80 7 90 8 100 9 110 10 120
6 10 10 8 20 6 30 4 40 2 50 1 60
9 10 10 9 20 8 30 7 40 6 50 5 60 4 70 5 80 6 90
5 6 60 7 70 8 80 9 90 10 110
5 2 10 4 20 6 30 8 40 10 50


Sample Output
------ ------

-- SAMPLE 1 --
50
-- SAMPLE 2 --
110


File:	   spacetravel.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Sat Oct  7 14:08:33 EDT 2017

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.