//仿照別人的思想敲得,之前不是很了解dijkstra，做過這題后有些理解
//1,將當(dāng)前未納入最短路的符合要求的距離最短結(jié)點(diǎn)納入最短路;
//2,將所有與當(dāng)前納入的結(jié)點(diǎn)有關(guān)聯(lián)并且未被納入最短路的結(jié)點(diǎn)最短距離進(jìn)行更新。
//圖論中另一個(gè)求最小生成樹的的經(jīng)典算法Prim算法與Dij過程極其類似，都是貪心思想。
//只是一個(gè)是對(duì)頂點(diǎn)的選擇，另外一個(gè)是對(duì)邊的選擇。
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)//判斷所交易的人的等級(jí)是否符合題目所述的條件
used[j]=1;//不符合
else
used[j]=0; //符合
dijkstra();
if(result>dis[1]) //比較每次所求的費(fèi)用
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++)//找出代價(jià)最小的邊
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++)//更新其節(jié)點(diǎn)的值
if(used[j]==0 && e[k][j]>0 && min+e[k][j]<dis[j])
dis[j]=min+e[k][j];
}
}
}
