// Arup Guha
// 11/6/2013
// Solution to 2013 South East Regional D1,D2 Problem D: Electric Car Rally

import java.util.*;

public class rally {

	public final static int START = 720;
	public final static int MAXCHARGE = 480;
	public final static int END = 1439;
	public final static int MAX = 1000000000;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int v = stdin.nextInt();
		int e = stdin.nextInt();

		// Read in each case.
		while (v != 0) {

			// Store graph as edge list.
			ArrayList[] graph = new ArrayList[v];
			for (int i=0; i<v; i++)
				graph[i] = new ArrayList<edge>();

			// Read in each edge.
			for (int i=0; i<e; i++) {

				// s -> e is edge.
				int start = stdin.nextInt();
				int end = stdin.nextInt();

				// Read in information about each time...
				ArrayList<Integer> startT = new ArrayList<Integer>();
				ArrayList<Integer> dist = new ArrayList<Integer>();
				while (true) {
					int t1 = stdin.nextInt();
					int t2 = stdin.nextInt();
					int d = stdin.nextInt();
					startT.add(t1);
					dist.add(d);
					if (t2 == END) break;
				}

				// Add this edge to the appropriate list.
				graph[start].add(new edge(end, startT, dist));
				graph[end].add(new edge(start, startT, dist));
			}

			System.out.println(solve(graph, MAXCHARGE));

			// Get next case.
			v = stdin.nextInt();
			e = stdin.nextInt();
		}
	}

	public static int solve(ArrayList[] graph, int source) {

		// Store estimates for all (vertex, charge) pairs in index 500*vertex + charge.
		int n = graph.length;
		dnode[] estimates = new dnode[n*500];

		// Set up estimates array.
		for (int i=0; i<estimates.length; i++)
			estimates[i] = new dnode(i, MAX);
		estimates[source] = new dnode(source, 720);

		// Put each node in the priority queue.
		PriorityQueue<dnode> pq = new PriorityQueue<dnode>();
		for (int i=0; i<estimates.length; i++)
			pq.add(estimates[i]);

		int[] ans = new int[n];
		Arrays.fill(ans, MAX);
		ans[0] = START;
		int nodesDone = 0;

		// Run Dijkstra's here.
		while (pq.size() > 0) {

			// Get the next item.
			dnode next = pq.poll();

			// Extract next vertex and charge in queue.
			int v1 = next.ID/500;
			int charge = next.ID%500;

			// Store this distance as final - first time we've gotten here.
			if (ans[v1] == MAX) {
				ans[v1] = next.dist;
				if (v1 == n-1) return ans[v1]-720;
			}

			// Try relaxing each edge here.
			for (int j=0; j<graph[v1].size(); j++) {
				edge e = (edge)graph[v1].get(j);
				relax(v1, e, charge, next.dist, pq, estimates);
			}
		}

		// Should never get here, but just in case...
		return ans[n-1] - START;
	}

	// Updates from vertex v1 using edge e. Essentially carries out the single if in Dijkstra's adjusted for the
	// weird edge system.
	public static void relax(int v1, edge e, int charge, int curDist, PriorityQueue<dnode> pq, dnode[] estimates) {

		int saveC = charge, saveD = curDist;

		// Try relaxing each possible edge in this list, for different times of day.
		for (int i=0; i<e.r.n; i++) {

			// Need to save the original version.
			charge = saveC;
			curDist = saveD;

			// Can't take this edge.
			if (e.r.distance[i] > 240) continue;

			// Set start and end.
			int nextD;
			int first = e.r.startTime[i], last;
			if (i == e.r.n-1) last = END;
			else			  last = e.r.startTime[i+1] - 1;

			// When we are first ready to go.
			int ready = Math.max(curDist, curDist+Math.max(0,2*e.r.distance[i]-charge));
			if (ready%1440 >= first && ready%1440 <= last) {
				nextD = ready + e.r.distance[i];
				charge = Math.max(0, charge-2*e.r.distance[i]);
			}

			// We have to wait until later in this day to take this edge.
			else if (ready%1440 < first) {
				nextD = ready + first - ready%1440 + e.r.distance[i];
				charge = Math.min(480, charge + nextD - e.r.distance[i] - curDist);
				charge -= 2*e.r.distance[i];
			}

			// We have to wait until tomorrow to take this edge.
			else {
				nextD = ready + 1440 - ready%1440 + first + e.r.distance[i];
				charge = Math.min(480, charge + nextD - e.r.distance[i] - curDist);
				charge -= 2*e.r.distance[i];
			}

			// Update based on this edge.
			if (nextD < estimates[e.dest*500 + charge].dist) {
				pq.remove(estimates[e.dest*500 + charge]);
				estimates[e.dest*500 + charge].dist = nextD;
				pq.add(estimates[e.dest*500 + charge]);
			}
		}
	}
}

class edge {

	public int dest;
	public int slots;
	public road r;

	public edge(int mydest, ArrayList<Integer> start, ArrayList<Integer> dist) {
		dest = mydest;
		r = new road(start, dist);
		slots = r.n;
	}
}

class road {

	public int[] startTime;
	public int[] distance;
	public int n;

	public road(ArrayList<Integer> start, ArrayList<Integer> dist) {
		n = start.size();
		startTime = new int[n];
		distance = new int[n];
		for (int i=0; i<n; i++) {
			startTime[i] = start.get(i);
			distance[i] = dist.get(i);
		}
	}
}

// Node for Dijkstra's heap
class dnode implements Comparable<dnode> {

	public int ID;
	public int dist;

	public dnode(int v, int d) {
		ID = v;
		dist = d;
	}

	public int compareTo(dnode other) {
		return this.dist - other.dist;
	}
}