import java.io.*;
import java.util.*;
import java.awt.geom.*;

/**
 * Solution to Electric Car Rally
 * 
 * There are two tricks we'll use. First, the easy one. Each 'road'
 * can have different weights at different times. We'll consider each
 * time slot to be a separate 'road'.
 * 
 * Now, the tough one. This is obviously a candidate for Dijkstra's shortest
 * path algorithm, with 'minutes' being the distance measure. But, there's a catch.
 * In Dijkstra, once you visit a node, you never visit it again. That won't
 * work for this problem. Consider visiting a station at time t with an empty
 * battery. What if you visit that same station at time t+1 with a nearly full battery?
 * The t+1 visit might yield a better overall result than the time t visit! So, we've
 * got to modify Dijkstra.
 * 
 * We'll create a threshold of time when we're still willing to visit a station.
 * That threshold will be the earliest time the car could leave with a fully charged
 * battery. That'll be minutes+480-charge. If that's less than our threshold, we'll visit the node.
 * We'll still sort the nodes by visit time, because ultimately, we want to know the earliest
 * time we can get to station n-1 without regard to battery charge.
 * 
 * @author vanb
 */
public class rally_vanb
{
    public Scanner sc;
    public PrintStream ps;
    
    /**
     * A Road, with endpoints, start and stop times, and time to travel.
     * 
     * @author vanb
     */
    public class Road
    {
        // Endpoints
        public int a, b;
        
        // Start/Stop times, travel time
        public int start, stop, time;
        
        /**
         * Create a Road.
         * 
         * @param a Station at one end
         * @param b Station at the other end
         * @param start Start time
         * @param stop Stop time
         * @param time Travel time
         */
        public Road( int a, int b, int start, int stop, int time )
        {
            this.a = a;
            this.b = b;
            this.start = start;
            this.stop = stop;
            this.time = time;
        }
        
        /**
         * The 'other' station.
         * 
         * @param s A station at one end of this road.
         * @return The station at the other end.
         */
        public int other( int s )
        {
            return s==a ? b : a;
        }
        
        /**
         * A pretty String for debugging.
         * 
         * @return A Pretty String
         */
        public String toString()
        {
            return "{" + a + "-" + b + ", " + start + ", " + stop + ", " + time + "}";
        }
    }
    
    /**
     * This is a State of the (modified) Dijkstra algorithm.
     * 
     * @author vanb
     */
    public class State implements Comparable<State>
    {
        // What station we've reached
        public int station;
        
        // How long we've been traveling, in total
        public int minutes;
        
        // Charge in our battery upon arrival
        public int charge;
        
        /**
         * Create a state.
         * 
         * @param s Station
         * @param m Minutes
         * @param c Charge
         */
        public State( int s, int m, int c )
        {
            station = s;
            minutes = m;
            charge = c;
        }
        
        /**
         * Compare this State to another, solely by minutes.
         * 
         * @param s Another State
         * @return -1, 0 or 1, as per the norm for compareTo()
         */
        public int compareTo( State s )
        {
            return minutes - s.minutes;
        }
    }
        
    /**
     * Driver.
     * @throws Exception
     */
    public void doit() throws Exception
    {
        sc = new Scanner( System.in ); //new File( "rally.judge" ) );
        ps = System.out; //new PrintStream( new FileOutputStream( "rally.vanb" ) );
        
        // All we really need to keep track of for stations
        // is a list of Roads.
        LinkedList<Road>[] stations = new LinkedList[500];
        for( int i=0; i<500; i++ )
        {
            stations[i] = new LinkedList<Road>();
        }
        
        // This array will hold the thresholds for the stations,
        // as described above.
        int thresh[] = new int[500];
        
        // A queue!
        PriorityQueue<State> pq = new PriorityQueue<State>();

        for(;;)
        {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if( n==0 && m==0 ) break;
            
            // Clear the existing stations, rather than recreating them
            for( int i=0; i<n; i++ )
            {
                stations[i].clear();
            }
            
            // Read in the roads
            for( int i=0; i<m; i++ )
            {
                int a = sc.nextInt();
                int b = sc.nextInt();
                int start, stop, time;
                do
                {
                    start = sc.nextInt();
                    stop = sc.nextInt();
                    time = sc.nextInt();
                    
                    // This is also a little tricky. Fully charged,
                    // the car cannot go longer that 240 minutes.
                    // Therefore, any road that takes longer than 240
                    // minutes can be ignored.
                    if( time<=240 )
                    {
                        // Create a separate 'Road' for each time interval
                        Road road = new Road( a, b, start, stop, time );
                        stations[a].add( road );
                        stations[b].add( road );
                    }
                } while( stop<1439 );
            }
            
            // Start with MaxInt as the threshold for all stations
            Arrays.fill( thresh, Integer.MAX_VALUE );

            pq.clear();
            
            // Start at station 0, time 0, fully charged battery with 480 minutes of charge
            pq.add( new State( 0, 0, 480 ) );
            int best = 0;
            while( !pq.isEmpty() )
            {
                State s = pq.poll();
                
                // If we've made it to the end, hooray!
                if( s.station==n-1 )
                {
                    best = s.minutes;
                    break;
                }
                
                // If our time of departure with a full charge is better than the current threshold,
                // then we should visit this station.
                if( s.minutes + 480 - s.charge <= thresh[s.station] )
                {
                    // Set the threshold
                    thresh[s.station] = s.minutes + 480 - s.charge;

                    // Current clock time. We've got to add 720
                    // because the rally starts at noon, not midnight.
                    int currenttime = (s.minutes+720) % 1440;

                    // Which roads could we use from here?
                    for( Road road : stations[s.station] )
                    {
                        // This is the station the road goes to
                        int t = road.other( s.station );
                        
                        // This is the number of minutes we must wait before departing.
                        int wait = 0;
                        if( currenttime < road.start )
                        {
                            // If we're here before the start time,
                            // wait until the start time.
                            wait = road.start - currenttime;
                        }
                        else if( currenttime > road.stop )
                        {
                            // If we're here after the end time, then
                            // we've got to hang around until the next day.
                            wait = road.start - currenttime + 1440;                            
                        }

                        // This is the minutes of charge we'll have after waiting
                        int newcharge = Math.min( s.charge + wait, 480 );
                        
                        // Is it enough to travel this road?
                        // Remember, 1 minute of travel requires 2 minutes of charge.
                        if( road.time*2 <= newcharge )
                        {
                            // If so, put this state on the queue!
                            // t is the new station
                            // s.minutes+wait+road.time is the time we'll arrive at station t
                            // newcharge-road.time*2 is the amount of charge we'll have left when we get to station t
                            pq.add( new State( t, s.minutes+wait+road.time, newcharge-road.time*2 ) );
                        }
                        else
                        {
                            // We didn't have enough charge to use this road. 
                            // How long must we wait until we do?
                            // How many more minutes of charge do we need?
                            int need = road.time*2 - newcharge;
                            
                            // We've got to wait that much longer.
                            wait += need;
                            
                            // This is our new time of departure
                            int depart = (currenttime + wait) % 1440;
                            
                            // The rest is the same as above.
                            if( depart < road.start )
                            {
                                wait += road.start - depart;
                            }
                            else if( depart > road.stop )
                            {
                                wait += road.start - depart + 1440;                            
                            }
 
                            newcharge = Math.min( s.charge + wait, 480 );
                            pq.add( new State( t, s.minutes+wait+road.time, newcharge-road.time*2 ) );
                        }
                    }
                }
            }
            
            ps.println( best );
            
        }
    }
    
    /**
     * @param args
     */
    public static void main( String[] args ) throws Exception
    {
        new rally_vanb().doit();        
    }   
}