P16040 [CSPro 22] 疫苗运输

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

X 市最近生产了一批疫苗，需要运往各地使用。疫苗的运输是一个困难的问题：既要实现尽快时间送达，又要保证全程冷链，否则疫苗会损坏。 X 市的物流系统并不发达，只有 $n$ 个**物流站点**（以下简称“站点”）和 $m$ 条**物流线路**（以下简称“线路”），且该物流系统具有以下几个特点： 1. 每条线路都是环线。即，从某个站点出发，经过一系列不重复的站点，最终回到出发站点。 2. 每条线路上有且仅有一辆**运输车**，以固定的时刻表（相邻站间的时间间隔）在环线上不断运行。在 0 时刻时，运输车在出发站点。 3. 运输车上配备了容量足够大的制冷系统，疫苗可以在车上长时间存放。但是**换乘**（从一条线路切换到另一条线路）必须在同一个站点同一个时刻发生——因为各个站点没有独立的制冷系统，疫苗不能在站点内下车等待。 现在 X 市想要从 $1$ 号站点开始，经过若干条线路的运输和换乘，将疫苗运输到各个其他站点。与其他站点不同，$1$ 号站点配有冷库。也就是说，从 $0$ 时刻开始，可以在 $1$ 号站点等待某条线路运输车的到来，再开始疫苗运输。问对于 $2$ 号 $\sim n$ 号站点，分别最早可以在什么**时刻**将疫苗送到该站点。 注意：每个问题是独立的，即只需要求出 $1$ 号站点到各个站点的最早送达时刻。

从标准输入读入数据。 第一行两个整数 $n, m$。 接下来 $m$ 行，每行表示一条物流线路。对于第 $i$（$1 \leq i \leq m$）条线路，首先有一个整数 $l_i$（$2 \leq l_i \leq n$）表示该线路经过的站点个数。接下来 $2l_i$ 个整数，第 $2j-1$ 和第 $2j$ 个整数分别表示该线路的第 $j$（$1 \leq j \leq l_i$）个站点的编号 $a_{i,j}$（$1 \leq a_{i,j} \leq n$），以及该线路的第 $j$ 个站点到下一个站点所需的时间 $t_{i,j}$（$1 \leq t_{i,j} \leq T$）（对于第 $l_i$ 个站点即为它到第 1 个站点的时间）。其中，每条线路的第 1 个站点为其出发站点。输入中同一行相邻的整数，均用一个空格隔开。

输出 $n-1$ 行，第 $i$ 行表示将疫苗送达第 $i+1$ 个站点的最早时间：如果能在有限时间内送达，输出最早的送达时刻；否则输出 inf。

### 样例 2 解释 在此样例中，有 5 个站点、3 条线路。第一条线路经过站点 1、2、3，第二条线路经过站点 3、4、5，第三条线路经过站点 3 和 5。 以下为从 1 号站点到各个其他站点的最早送达路线： - 2 号站点：通过第一条线路运输，在 $100$ 时刻到达 2 号站点 - 3 号站点：通过第一条线路运输，在 $200$ 时刻到达 3 号站点 - 4 号站点：通过第一条线路运输，在 $500$ 时刻到达 3 号站点，然后换乘第三条线路，在 $1500$ 时刻再次到达 3 号站点，最后换乘第二条线路，在 $1600$ 时刻到达 4 号站点 - 5 号站点：通过第一条线路运输，在 $500$ 时刻到达 3 号站点，然后换乘第三条线路，在 $625$ 时刻到达 5 号站点 ### 子任务 对于 $10\%$ 的数据，$n \leq 5$, $m = 1$, $T \leq 10$。 对于 $30\%$ 的数据，$n \leq 5$, $m \leq 2$, $T \leq 10$。 对于 $50\%$ 的数据，$n \leq 5$, $m \leq 5$, $T \leq 10$。 对于 $70\%$ 的数据，$n \leq 10$, $m \leq 10$, $T \leq 100$。 对于 $80\%$ 的数据，$n \leq 30$, $m \leq 30$, $T \leq 1000$。 对于 $95\%$ 的数据，$n \leq 100$, $m \leq 100$, $T \leq 10^5$。 对于 $100\%$ 的数据，$n \leq 500$, $m \leq 500$, $T \leq 10^6$。