Description

I have an undirected weighted graph with $n$ nodes. It has many edges, and it is represented in the following way:

• There are $k$ sets. The $i$-th set can be written as $S_i=\{(T_1,W_1),(T_2,W_2),\dots,(T_{|S_i|},W_{|S_i|})\}$.
• For any two pairs $(T_i,W_i),(T_j,W_j)$ in the same set, the graph will contain an edge connecting $T_i$ and $T_j$, with edge weight $W_i+W_j$.

For every node $i$, find the shortest path from $1$ to $i$, i.e., a simple path from $1$ to $i$ with the minimum total edge-weight sum.

Input Format

The first line contains two positive integers $n,k$.
Next, describe the $k$ sets.
The first line of the description of set $i$ contains a positive integer $|S_i|$, which is the size of $S_i$.
Then follow $|S_i|$ lines, each containing two positive integers $t,w$, meaning $(t,w)\in S_i$.

Output Format

Output one line with $n$ positive integers. The $i$-th positive integer is the length of the shortest path from $1$ to $i$. If no path exists, output $\textsf{0x3f3f3f3f3f3f3f3f}=4557430888798830399$.

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

0 2 5 4 4

Hint

For the first $10\%$ of the testdata, $|S_i|=2$.
For the first $20\%$ of the testdata, $|S_i|\le10$.
For the first $50\%$ of the testdata, $|N|\le1000,\sum|S_i|\le2000$.
For $100\%$ of the testdata, $1\le|N|\le2\cdot10^5,\sum|S_i|\le4\cdot10^5,0\le W_i\le10^9$.

Translated by ChatGPT 5