#include <string>
#include <iostream>
#include <vector>
using namespace std;
#define INF 2147483647//用inf(infinity的缩写)存储一个我们认为的正无穷值

int main(void) {
    int limit,n;
    while ( cin >> limit >> n ){
    if(n==0)return 0;
    int *status=new int[n];//访问状态
    int *dis=new int[n];//距离
    int **path=new int*[n];
    int *level=new int[n];
    int *value=new int[n];
    for(int i=0;i<n;i++)
    {
        path[i]=new int[n];

        for(int j=0;j<n;j++)
        {
            path[i][j]=INF;
        }
        status[i]=1;
        path[i][i]=0;
    }
    int result=INF;
    for(int i=0;i<n;i++)
    {
        cin>>value[i];
        cin>>level[i];
        int temp;
        cin>>temp;
        for(int j=0;j<temp;j++)
        {
            int parm;
            cin>>parm;
            cin>>path[i][parm-1];
        }

    }
    for(int i=0;i<n;i++)
    {
        dis[i]=INF;
        //cout<<dis[i]<<endl;
    }
    int high=level[0]+limit;
    int low=level[0];

    int num=0;
    for(int t=0;t<=limit;t++)
    {
        num=0;
        for(int i=0;i<n;i++)//初始化
        {
            status[i]=1;
            dis[i]=path[0][i];
        }
        dis[0]=value[0];
        low=level[0]-t;
        high=level[0]+limit-t;
        for(int i=0;i<n;i++)//设定子图
        {
            if(level[i]<=high&&level[i]>=low){
                status[i]=0;
                num++;
            }
        }
        //开始dijk

        for(int i=0;i<num;i++)
        {
            int minDis=INF;
            int index=0;
            for(int j=0;j<n;j++)
            {
                if(minDis>dis[j]&&status[j]==0){
                    minDis=dis[j];
                    index=j;
                }
            }

            status[index]=1;
            for(int k=0;k<n;k++)
            {
                    if(status[k]==0&&dis[k]>dis[index]+path[index][k]-value[index]+value[k]){
                       dis[k]=dis[index]+path[index][k]-value[index]+value[k];
                    }

            }

        }
        for(int i=0;i<n;i++)
        {
            if(result>dis[i])
                result=dis[i];
        }

    }

    cout<<result<<endl;
    for(int i=0;i<n;i++)
    {
        delete[] path[i];
    }
    delete[] path;
    delete[] status;
    delete[] dis;
    delete[] level;
    delete[] value;
    }
	return 0;
}