P7100 [W1] Group

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.

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 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$.

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