题目描述

我有一张 $n$ 个节点的无向边带权图。它的边很多，用这个方法表示：

• 有 $k$ 个集合；第 $i$ 个集合可以表示为 $S_i=\{(T_1,W_1),(T_2,W_2),\dots,(T_{|S_i|},W_{|S_i|})\}$。
• 对于任何两对 $(T_i,W_i),(T_j,W_j)$ 在同一个集合里面，图中会形成一条连 $T_i$ 和 $T_j$ 的边，边权为 $W_i+W_j$。

请对于所有节点 $i$ 找到 $1$ 到 $i$ 的最短路，即从 $1$ 到 $i$ 的边权和最小的简单路径。

输入格式

第一行两个正整数 $n,k$。
接下来描述 $k$ 个集合。
第 $i$ 集合的描述的第一行一个正整数 $|S_i|$，表示 $|S_i|$ 的大小。
接下来 $S_i$ 行，每行两个正整数 $t,w$，表示 $(t,w)\in S_i$。

输出格式

一行 $n$ 个正整数；第 $i$ 个正整数表示 $1$ 到 $i$ 的最短路长度。如果不存在一条路径，输出 $\textsf{0x3f3f3f3f3f3f3f3f}=4557430888798830399$。

5 2
3
1 1
2 1
5 3
3
2 1
3 2
4 1

0 2 5 4 4

提示

对于前 $10\%$ 的数据，$|S_i|=2$；
对于前 $20\%$ 的数据，$|S_i|\le10$；
对于前 $50\%$ 的数据，$|N|\le1000,\sum|S_i|\le2000$;
对于 $100\%$ 的数据，$1\le|N|\le2\cdot10^5,\sum|S_i|\le4\cdot10^5,0\le W_i\le10^9$。