'''
建图方式
构造一个虚拟节点0, 0 到每一个物品的边权是物品本来价格,然后每个物品的可替代物品到
被替代物品间边权值是替代价格,问题转换成求0号点到1号点的最短距离,合法的方案中一定是
所有方案的等级差值在M以内,所以枚举所有长度是M+1的连续等级区间,每个区间选出在区间
中的物品,用这些物品构造有向图求最短距离,找出每个区间对应的最短距离的最小值即可
'''
from collections import deque
class SPFA:
# start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num
# 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getMinInfo()
def getMinInfo(self):
link = {}
dis = [0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0
for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if w < 0:
return None
if a not in link:
link[a] = []
if b not in link:
link[b] = []
link[a].append((b, w))
link[b].append((a, w))
else:
if a not in link:
link[a] = []
link[a].append((b, w))
updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1
# 进行V次迭代,第V次检查是否是无解情况
iter_times = 0
while iter_times < self.max_node_num:
update_flag = False
# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
if a not in link:
continue
for b, w in link[a]:
new_dis = 0x7fffffff if dis[a] == 0x7fffffff else dis[a] + w
if new_dis < dis[b]:
dis[b] = new_dis
update_flag = True
if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)
iter_times += 1
if iter_times == self.max_node_num:
if update_flag:
return None
if not update_flag:
break
return [[node, dis[node]] for node in range(1, self.max_node_num+1)]
M, N = map(int, input().split())
product = [[0, 0, []] for _ in range(N+1)]
for i in range(1, N+1):
product[i][0], product[i][1], x = map(int, input().split())
product[i][2] = []
for _ in range(x):
t, v = map(int, input().split())
product[i][2].append((t, v))
min_cost = 0x7fffffff
for lower in range(product[1][1] - M, product[1][1] + 1):
upper = lower + M
edges = []
for i in range(1, N+1):
if product[i][1] >= lower and product[i][1] <= upper:
edges.append( (0, i, product[i][0]) )
for id, price in product[i][2]:
if product[id][1] >= lower and product[id][1] <= upper:
edges.append( (id, i, price) )
edges.append( (0, id, product[id][0]) )
algo = SPFA(0, edges, is_directed=True, max_node_num = N)
ans = algo.getMinPathLen()
for k, v in ans:
if k == 1:
min_cost = min(min_cost, v)
break
print(min_cost)