//是/Dij算法，求单源最短路径。刚开始做连结果都打不出来，主要是对等级的处理， 原以为酋长等级L，那么只要周围的等级比他低就行了，直接在建图的时候把比酋长高的等级的节点删去
//就可以了，当时一直WA。后来才发现如果限制等级是M，那么就M+1种情况。比如：L=5，M=2，那么所有的情况为：
//3-5,4-6,5-7这种情况。因此对这M+1种情况逐一枚举，求最小。修改后发现还是不出结果，原来建图错误，方向搞
//错了，接下来就是一天半的RE，怎么改都是，索性扔那不管了。最后加了3条memset语句就过了，看来初始化还是有
//必要的啊。下面给出等级的判断式：
//level = true if(rank[i]>=t && rank[i]=<M+L 其中t是从L-M到L） 否则为false.
//M，N
//P、L、X
/*1 4
10000 3 2
2 8000
3 5000
1000 2 1 
4 200
3000 2 1
4 200
50 2 0*/
#include <iostream>
#include <cstring>
#define Inf 999999
using namespace std;
int G[101][101],D[101],rank[101],X,flag[1002]; 
int M,N,L;
void init()   // 图论的输入有时很麻烦，避免混乱，还是先初始化好。
{
  int t,x,y;       
  for(int i=1;i<=N;i++)   
    {   
        for(int j=1;j<=N;j++)   
           {              
            G[i][j] = Inf;                                    
           }        
    }    
  for(int i=1;i<=N;i++)    
    {           
     cin>>G[0][i]>>rank[i]>>X;   
     for(int j=0;j<X;j++)  
       {               
          cin>>x>>y;               
          G[x][i] = y;                                   
       }              
    }  
   L = rank[1];                                                    
}//end init
int Dij()
{      
           int answer = Inf,min,v;       
 for(int t=L-M;t<=L;t++)  //对着M+1种情况枚举       
   {          
           for(v=1;v<=N;v++)   //开始经典的Dij啦        
           {       
             D[v] = G[0][v];      
             flag[v] = false;                                     
           }   
           flag[0] = true;
           D[0]=0;                
           for(int w=1;w<=N;w++)          
            {       
               min = Inf;            
               for(int j=0;j<=N;j++)          
                 {          
                    if(!flag[j] && D[j]<min && rank[j]<=t+M && rank[j]>=t)//注意这里对等级的判定
                          {                   
                          min = D[j];             
                          v = j;                    
                          }                              
                 }                                        
               flag[v] = true;              
               for(int k=0;k<=N;k++)              
                 {          
                   if(!flag[k] && min+G[v][k]<D[k] && rank[k]>=t && rank[k]<=t+M)//注意等级判定 
                      {         
                                D[k] = min+G[v][k];      
                      }
                 }                           
           }          
                              
           if(D[1]<answer) answer = D[1];
  }                    
  return answer;       
}
int main()
   {      
   int answer,temp;     
   while(cin>>M>>N)      
   {           
      memset(D,0,sizeof(D));   
      memset(rank,0,sizeof(rank));     
      memset(flag,false,sizeof(flag)); //这三条memset害得我好惨 
      init();     
      answer = Dij();    
      cout<<answer<<endl;     
   }
   return 0;    
}