import java.util.Scanner;

public class Main {

	public final static int MAX_VALUE = 99999999;

	int M;
	int N;
	int length;
	People[] peoples;
	int min;
	int max;

	public Main(int M, int N) {
		this.M = M;
		this.N = N;
		peoples = new People[N + 1];
		for (int i = 0; i <= N; i++)
			peoples[i] = new People(i);

	}

	public People createPeople(int id, int level) {
		peoples[id].setLevel(level);
		return peoples[id];
	}

	public Edge createEdge(int id, int length) {
		return new Edge(id, length);
	}

	public void recovery() {
		// System.out.println("this min:"+min+" max:"+max);
		peoples[0].isVisit = false;
		for (int i = 1; i <= N; i++) {
			peoples[i].setLength(MAX_VALUE);
			peoples[i].isVisit = false;
		}
	}

	public class People {
		int id;
		int level;
		int length;
		Edge head;
		Edge tail;
		boolean isVisit;

		public People(int id) {
			this.id = id;
		}

		public void append(Edge edge) {
			if (head == null) {
				head = edge;
				tail = edge;
			} else {
				this.tail.next = edge;
				this.tail = edge;
			}
		}

		public boolean isSuitable(int length) {
			if (this.length < length && !isVisit && this.level >= min
					&& this.level <= max)
				return true;
			return false;
		}

		public void setLevel(int level) {
			this.level = level;
		}

		public void setLength(int length) {
			this.length = length;
		}

	}

	public class Edge {
		int id;
		int length;
		Edge next=null;

		public Edge(int id, int length) {
			this.id = id;
			this.length = length;
		}

	}

	public People getSuitablePeople() {
		int length = MAX_VALUE+1;
		People people = null;
		for (int i = 0; i < peoples.length; i++) {
			if (peoples[i].isSuitable(length)) {
				length = peoples[i].length;
				people = peoples[i];
			}
			// System.out.println(i + " " + peoples[i].length);
		}
		people.isVisit = true;
		return people;
	}

	public int getMinLength() {
		while (!peoples[1].isVisit) {
			People people = getSuitablePeople();
			// System.out.println("Suitable id:" + people.id);
			Edge edge = people.head;
			while (edge != null) {
				if (people.length + edge.length < peoples[edge.id].length) {
					peoples[edge.id].length = people.length + edge.length;
				}
				edge = edge.next;
			}
		}
		return peoples[1].length;
	}

	public int getMostMinLength(int min, int max) {
		int length = MAX_VALUE;
		peoples[0].level =peoples[1].level;
		for (int i = min; i <= max - M; i++) {
			this.min = i;
			this.max = i + M;
			if (this.min + M < peoples[1].level)
				continue;
			if (this.min > peoples[1].level)
				break;
			recovery();
			if (length > getMinLength()) {
				length = getMinLength();
			}
		}

		return length;
	}

	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int M, N;
		int min = MAX_VALUE, max = 0;
		M = scanner.nextInt();
		N = scanner.nextInt();
		Main main = new Main(M, N);
		for (int i = 1; i <= N; i++) {
			int P, L, X;
			P = scanner.nextInt();
			L = scanner.nextInt();
			if (L < min)
				min = L;
			if (L > max)
				max = L;
			X = scanner.nextInt();
			People people = main.createPeople(i, L);
			Edge edge = main.createEdge(i, P);
			main.peoples[0].append(edge);
			for (int j = 0; j < X; j++) {
				int T, V;
				T = scanner.nextInt();
				V = scanner.nextInt();
				Edge edge1 = main.createEdge(T, V);
				people.append(edge1);
				Edge edge2 = main.createEdge(i, V);
				main.peoples[T].append(edge2);
			}
		}
		System.out.println(main.getMostMinLength(min, max));
	}

}


感觉没什么问题啊啊  怎么老WA 呢