Shortest Paths in a Weighted Graph with Group Edges

You are given an undirected weighted graph with n nodes. However, the graph is not given explicitly. Instead, the edges are represented by k groups. For each group i, you are given a set

[ S_{i}={(T_{1},W_{1}),(T_{2},W_{2}),\dots,(T_{|S_{i}|},W_{|S_{i}|})} ]

For every two distinct pairs \((T_p,W_p)\) and \((T_q,W_q)\) inside the same group, an undirected edge is added between nodes \(T_p\) and \(T_q\) with weight:

[ \text{weight}(T_p, T_q)=W_{p}+W_{q} ]

Your task is to compute, for every node \(i\) from \(1\) to \(n\), the minimum total weight (i.e. the sum of the weights of its edges) along any simple path from node \(1\) to node \(i\). If a node is unreachable from node \(1\), output -1 for that node.

Hint: To avoid constructing the complete graph explicitly (since each group induces many edges), you might consider an alternative modeling. For instance, you can add an auxiliary node for each group. For every pair \((v, W)\) in a group, add an edge from node \(v\) to the auxiliary node with weight \(W\) and an edge from the auxiliary node back to \(v\) with the same weight. Then, a path from \(u\) to \(v\) passing through this auxiliary node has cost \(W_u+W_v\), which is exactly the cost of the edge between \(u\) and \(v\) in that group.

inputFormat

The input consists of several lines:

1. The first line contains two integers \(n\) and \(k\) where \(n\) is the number of nodes and \(k\) is the number of groups.
2. Then follow \(k\) groups. For each group, the first integer is \(m\), the number of pairs in the group, followed by \(m\) pairs of integers \(T\) and \(W\), where \(T\) is the node index (1-indexed) and \(W\) is the weight associated with that node in the group.

You may assume that all numbers are space-separated.

outputFormat

Output a single line with \(n\) space-separated integers. The \(i\)th integer should be the length of the shortest path from node 1 to node \(i\), or -1 if node \(i\) is unreachable.

sample

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

0 3 5 7