T539768 「YAC Round 12」交叉星尘
题目背景
> 那个呢！ 就算是白天，星星也在哪里哦！
题目描述
椎名真由理所看到的星空中有 $n$ 个星星，并且有很多星星聚集在一起，构成了 $m$ 个星团。每个星团可以用一个集合 $P$ 来表示：
$$
P = \{(v_1, b_1), (v_2, b_2), \ldots, (v_{|P|}, b_{|P|}) \}
$$
其中 $v_i$ 表示星星的编号，$b_i$ 表示星星的相对亮度。
一个星星在一个星团中只会出现一次。但一个星星可能包含在不同的星团中，一个星星在不同星团中的相对亮度也不一定相同。
由于世界线收束，星团呈现出了独特的性质。对于 **同一个星团** $P$ 中的 **任意两个不同** 的星星 $(v_i, b_i)$ 和 $(v_j, b_j)$，$v_i$ 和 $v_j$ 之间有一条长度为 $b_i + b_j$ 的无向边。
对于每个星星 $i$，椎名真由理想要找到从 $1$ 到 $i$ 的 **最短路径的长度**。
输入格式
第一行输入两个整数 $n,m$（$1 \le n \le 2 \times 10^5$, $\sum |P| \le 4 \times 10^5$），分别表示星星的总数和星团的个数。
接下来描述 $m$ 个星团。对于第 $i$ 个星团集合：
第一行输入一个整数 $|P_i|$，表示当前这个星团 $P_i$ 中星星的个数。
接下来 $|P_i|$ 行，每行输入两个整数 $v, b$（$1 \le v \le n, 0 \le b \le 10^9$），分别表示每个星星的编号和亮度。
输出格式
输出一行 $n$ 个正整数。其中第 $i$ 个整数表示星星 $1$ 到 $i$ 的最短路径的长度。
如果星星 $1$ 到星星 $i$ 之间不可达，输出 $\text{0x3f3f3f3f3f3f3f3f}=4557430888798830399$。