nyist 510昂貴的聘禮

/*
好好的圖論題啊，最短路的應用，dijkstra算法 
*/
#include <iostream>
using namespace std;
const int INF=100000;
int a[105][105],b[105],c[105],s[105],dist[105];
int n,m;
int dj(int p,int q)
{
	int i,j,r,t,k=0;
	for(i=0;i<n;i++)
	if((b[i]>=p&&b[i]<=q)) dist[i]=a[k][i], s[i]=0; else dist[i]=INF,s[i]=0;
	dist[0]=0; s[0]=1;
	for(i=1;i<n;i++)
	{
		t=INF;
		for(j=0;j<n;j++)
		if(!s[j]&&dist[j]<t) t=dist[j],k=j;
		s[k]=1;
		for(j=0;j<n;j++)
		if(!s[j]&&a[k][j]<INF&&b[j]>=p&&b[j]<=q)
		{
			r=dist[k]+a[k][j];
			if(dist[j]>r) dist[j]=r;
		}
	}
	t=c[0];
	for(i=0;i<n;i++)
    if(dist[i]+c[i]<t) t=dist[i]+c[i];
		return t;
}
int main(int argc, char *argv[])
{
	int i,j,k,p,q,l,r;
	while(cin>>m>>n&&(m||n))
	{
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		a[i][j]=INF;
	for(i=0;i<n;i++)
	{
		
		cin>>c[i]>>b[i]>>k;
	    for(j=0;j<k;j++)
	    {
	    cin>>p>>q;
	    a[i][p-1]=q;
	    }
	}
	r=c[0];
     for(i=b[0]-m;i<=b[0];i++)
     {
	 k=dj(i,i+m);
	 if(k<r) r=k;
     }
     cout<<r<<endl;
	}
	return 0;
}