/**POJ 1062 昂贵的聘礼*代码参考: http://poj.org/showmessage?message_id=344843*/#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 110;const int INF = 0x3f3f3f3f;int dist[MAXN], edge[MAXN][MAXN], level[MAXN];bool visit[MAXN];int n, m;int dijkstra(){	int i, j;	for (i = 0; i <= n; i++) {		dist[i] = edge[0][i];	}	visit[0] = 1;	for (i = 1; i < n; i++) {		int min = INF;		int u = 0;		for (j = 1; j <= n; j++) {			if (!visit[j] && dist[j] < min) {				u = j;				min = dist[j];			}		}		visit[u] = 1;		for (j = 1; j <= n; j++) {			if (!visit[j] && edge[u][j] < INF && dist[u] + edge[u][j] < dist[j]) {				dist[j] = dist[u] + edge[u][j];			}		}	}	return dist[1];}int main(){	int i, j, num, temp;	while (~scanf("%d %d", &m, &n)) {		for (i = 0; i <= n; i++) {			for (j = 0; j <= n; j++) {				edge[i][j] = INF;			}			edge[i][i] = 0;		}		memset(level, 0, sizeof(level));		memset(visit, 0, sizeof(visit));		for (i = 1; i <= n; i++) {			scanf("%d %d %d", &edge[0][i], &level[i], &num);			for (j = 1; j <= num; j++) {				scanf("%d", &temp);				scanf("%d", &edge[temp][i]);			}		}		int ans = INF;		for (i = 1; i <= n; i++) {			int lv = level[i];			for (j = 1; j <= n; j++) {				if (level[j] > lv || lv - level[j] > m) {					visit[j] = 1;				} else {					visit[j] = 0;				}			}			int min = dijksttra();			if (ans > min) {				ans = min;			}		}		printf("%d\n", ans);	}	return 0;}