M国要在n个城市所组成的城市群内建设基站，工程师们已经考察从城市$i$（$1≤i≤n$）往城市$j$（$1≤j≤i$）$1,2,3,...,d_{ij}$（$d_{ij}$表示从城市i到城市j的距离）千米处的建设基站的成本，分别是$w_{ij1}$,$w_{ij2}$,$w_{ij3}$,...,$w_{ijd_{ij}}$。为保证通信质量，基站的选址还需要满足$m$条需求。第$i$条需求可以用$i$，$j$，$l$和$r$表示（$1≤j≤i≤n$,$1≤l≤r≤n$）,代表从城市$i$往城市$j$方向上$l$千米到$r$千米的位置之间（含两端）至少需要建设1座基站。
作为M国的总工程师，您需要决定基站的数量与位置，并计算满足所有需求的最小总成本。

第一行输入两个整数$n$（$1≤n≤5000$，$1≤m≤500000$）和$m$分别表示城市数量和需求数量。
接下来$2n$行一行输入3个整数$i,j$和$d_{ij}$（表示从城市$ i $到城市$ j $的距离），下一行输入$d_{ij}$个整数$w_{ij1}$,$w_{ij2}$,$w_{ij3}$,...,$w_{ijd_{ij}}$分别表示从城市$i$（$1≤i≤n$）往城市$j$（$1≤j≤i$）$1,2,3,...,d_{ij}$（$d_{ij}$表示从城市i到城市j的距离）千米处的建设基站的成本。
接下来m行