/*
 * electricRally_zeil.cpp
 *
 *  Created on: Oct 3, 2013
 *      Author: zeil
 */

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <limits>
#include <list>
#include <queue>
#include <vector>
#include <map>


using namespace std;


const int MaxTravelTime = 240;
const int MaxFuel = 2 * MaxTravelTime;
const int EntireDay = 24*60;


struct TravelTime {
	int startingTime;
	int endingTime;
	int travelTime;

	TravelTime (int start, int end, int duration)
	: startingTime(start), endingTime(end), travelTime(duration)
	{}
};

struct Connection {
	int destinationNum;
	list<TravelTime> travelOptions;

	Connection (int dest = 0)
	: destinationNum(dest)
	{}
};

istream& operator>> (istream& in, Connection& c)
{
	int start, stop, t;
	stop = -1;
	while (stop < 1439)
	{
		in >> start;
		if (start != stop + 1)
		{
			cerr << "Error: non-consecutive time intervals " << stop << " followed by ";
			in >> stop;
			cerr << start << ".." << stop << " traveling to " << c.destinationNum << endl;
			exit (1);
		}
		in >> stop >> t;
		c.travelOptions.push_back(TravelTime(start, stop, t));
	}
	return in;
}




struct Event {
	int time;
	int fuel;
	int arrivedAt;
	int cameFrom;
};
bool operator< (Event left, Event right)
{
	if (left.time > right.time)
		return true;
	else if (left.time == right.time)
	{
		if (left.fuel < right.fuel)
			return true;
		else if (left.fuel == right.fuel)
			return left.arrivedAt < right.arrivedAt;
	}
	return false;
}
ostream& operator<< (ostream& out, Event e)
{
	out << "event{" << e.cameFrom << "=>" << e.arrivedAt << ", t=" << e.time << ", f=" << e.fuel << "}";
	return out;
}





struct CheckPoint {
	Event bestSoFar;
	list<Connection> edges;

	CheckPoint()
	{
		Event init = {1000000, 0, 0, 0};
		bestSoFar = init;
	}
};





class Rally
{
   int numCheckPoints;
   CheckPoint* checkPoints;
public:

   Rally (int n, int m, istream& in);
   ~Rally();

   int computeTime();

   bool plausible (const Event& ev, CheckPoint& cp) const;

};

Rally::Rally (int n, int m, istream& in)
 : numCheckPoints(n)
{
	checkPoints = new CheckPoint[numCheckPoints];
	for (int i = 0; i < m; ++i)
	{
		int cp1, cp2;
		in >> cp1 >> cp2;
		if (cp1 == 0 && cp2 == 0)
		{
			cerr << "Error: premature end of input while reading edge " + i << endl;
			exit (1);
		}
		if (!in)
		{
			cerr << "Error reading edge " + i << endl;
			exit (1);
		}
		if (cp1 >= numCheckPoints || cp2 >= numCheckPoints)
			cerr << "Illegal edge  " << cp1 << "=>" << cp2 << endl;
		Connection edge (cp2);
		in >> edge;
		checkPoints[cp1].edges.push_back(edge);
		edge.destinationNum = cp1;
		checkPoints[cp2].edges.push_back(edge);
	}
}


Rally::~Rally(){
	delete [] checkPoints;
}



bool Rally::plausible (const Event& ev, CheckPoint& cp) const
{
	bool OK;
	if (ev.cameFrom == ev.arrivedAt)
	{
		OK = (ev.time <= cp.bestSoFar.time + EntireDay + MaxFuel);
	}
	else if (ev.arrivedAt == numCheckPoints - 1)
		return true;
	else
	{
		OK = (ev.time < cp.bestSoFar.time) || (ev.time - ev.fuel < cp.bestSoFar.time - cp.bestSoFar.fuel);
	}
	return OK;
}

void remember (const Event& ev, CheckPoint& cp)
{
	if (ev.cameFrom != ev.arrivedAt)
		cp.bestSoFar = ev;
}



int Rally::computeTime()
{
	Event rallyStart = {720, MaxFuel, 0};
	checkPoints[0].bestSoFar = rallyStart;
	remember(rallyStart, checkPoints[0]);
	priority_queue<Event> q;
	q.push(rallyStart);
	Event lastEvent = {0,0,0};
	while (!q.empty())
	{
		Event ev = q.top();
		cerr << "processing " << ev << endl;
		q.pop();
		if (ev.arrivedAt == lastEvent.arrivedAt && ev.time == lastEvent.time && ev.fuel == lastEvent.fuel)
		{
			continue;
		}
		lastEvent = ev;

		if (ev.arrivedAt == numCheckPoints - 1) {
			cerr << "final: " << ev << endl;
			return ev.time - 720;;
		}
		CheckPoint& loc = checkPoints[ev.arrivedAt];
		for (list<Connection>::iterator it = loc.edges.begin(); it != loc.edges.end(); ++it)
		{
			Connection& edge = *it;
			int timeOfDay = ev.time % EntireDay;
			list<TravelTime>::iterator tt = edge.travelOptions.begin();
			while (tt->endingTime < timeOfDay)
				++tt;
			TravelTime& option = *tt;
			cerr << "can go to " << edge.destinationNum << " in " << option.travelTime << " minutes" << endl;
			if (ev.fuel >= 2*option.travelTime)
			{
				// We have enough fuel to immediately take this road
				Event e2 = {ev.time + option.travelTime, ev.fuel - 2*option.travelTime, edge.destinationNum, ev.arrivedAt};
				if (plausible(e2, checkPoints[e2.arrivedAt]))
				{
					cerr << "pushing on " << e2 << endl;
					q.push(e2);
					remember(e2, checkPoints[e2.arrivedAt]);
				}
			}
			if (ev.fuel < 2*option.travelTime && 2*option.travelTime <= MaxFuel)
			{
				// Or we can wait till we have just enough fuel to push on
				Event e2 = {ev.time + (2*option.travelTime - ev.fuel), 2*option.travelTime, ev.arrivedAt, ev.arrivedAt};
				if (plausible(e2, checkPoints[e2.arrivedAt]))
				{
					cerr << "fueling " << e2 << endl;
					q.push(e2);
					remember(e2, checkPoints[e2.arrivedAt]);
				}

			}

			// Or we can hang around waiting for the traffic to clear up
			Event e3 = {ev.time + option.endingTime + 1 - timeOfDay,
					min(MaxFuel, ev.fuel + (option.endingTime + 1 - timeOfDay)),  ev.arrivedAt, ev.arrivedAt};
			if (plausible(e3, checkPoints[e3.arrivedAt]))
			{
				cerr << "waiting " << e3 << endl;
				q.push(e3);
				remember(e3, checkPoints[e3.arrivedAt]);
			}
		}
	}
	return 0;
}

void solve (istream& in)
{
   int N, M;
   in >> N;
   while (N > 0)
   {
	   in >> M;
	   //cout << N << " " << M << endl;
	   Rally rally (N, M, in);
	   int t = rally.computeTime();
	   cout << t << endl;
	   in >> N;
   }
}


int main (int argc, char** argv)
{
	if (argc > 1)
	{
		ifstream in (argv[1]);
		solve (in);
	}
	else
		solve(cin);
	return 0;
}