//仿照別人的思想敲得,之前不是很了解dijkstra，做過這題后有些理解
//1,將當前未納入最短路的符合要求的距離最短結點納入最短路;
//2,將所有與當前納入的結點有關聯并且未被納入最短路的結點最短距離進行更新。
//圖論中另一個求最小生成樹的的經典算法Prim算法與Dij過程極其類似，都是貪心思想。
//只是一個是對頂點的選擇，另外一個是對邊的選擇。
import java.util.*;
public class Main
{ public static int[][] e;
public static int[] dis;
public static int[] used;
public static int[] level;
public static int n,m;
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int x,t;
e = new int[101][101];
dis = new int[101];
used = new int[101];
level = new int[101];
m=cin.nextInt();
n=cin.nextInt();
for(int i=1;i<=n;i++)
{ e[0][i]=cin.nextInt();
level[i]=cin.nextInt();
x=cin.nextInt();
for(int j=0;j<x;j++)
{ t=cin.nextInt();
e[t][i]=cin.nextInt();
}
}
solve();
}
public static void solve()
{ int max,result;
result=e[0][1];
for(int i=1;i<=n;i++)
{ max=level[i];
for(int j=1;j<=n;j++)
if(level[j]>max || level[j]<max-m)//判斷所交易的人的等級是否符合題目所述的條件
used[j]=1;//不符合
else
used[j]=0; //符合
dijkstra();
if(result>dis[1]) //比較每次所求的費用
result=dis[1];
}
System.out.println(result);
}
public static void dijkstra()
{ int min,temp,k;
for(int i=1;i<=n;i++)
dis[i]=e[0][i];
for(int i=1;i<=n;i++)
{ min=0x7FFFFFFF;
k=0;
for(int j=1;j<=n;j++)//找出代價最小的邊
if(used[j]==0 && dis[j]<min)
{min=dis[j];
k=j;
}
if(k==0)
break;
used[k]=1;
for(int j=1;j<=n;j++)//更新其節點的值
if(used[j]==0 && e[k][j]>0 && min+e[k][j]<dis[j])
dis[j]=min+e[k][j];
}
}
}
