题目描述

我有一张 $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|\le10^3$，$\sum|S_i|\le2\times 10^3$;
对于 $100\%$ 的数据，$1\le|n|\le2\cdot10^5$，$\sum|S_i|\le4\cdot10^5$，$0\le w_i\le10^9$。