Cổng dịch chuyển

Có $n$ thành phố đánh số từ $1$ đến $n$ và $m$ con đường hai chiều; con đường thứ $i$ nối $u_i$ với $v_i$ và đi hết mất $w_i$ phút. Có thể có đường nối một thành phố với chính nó và nhiều đường nối cùng một cặp thành phố.

Ngoài ra còn có $k$ mạng dịch chuyển. Mạng thứ $j$ gồm $s_j$ thành phố khác nhau và có thời gian dịch chuyển $c_j$: từ bất kỳ thành phố nào của mạng, bạn có thể dịch chuyển tới bất kỳ thành phố nào khác của cùng mạng đó, mất $c_j$ phút. Một thành phố có thể thuộc nhiều mạng.

Xuất phát từ thành phố $1$, hãy tính thời gian ít nhất để tới từng thành phố.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.
• $k$ dòng tiếp theo, dòng thứ $j$ bắt đầu bằng hai số nguyên $c_j$, $s_j$, sau đó là $s_j$ số nguyên: các thành phố thuộc mạng $j$.

Dữ liệu ra

In ra $n$ số trên một dòng, số thứ $v$ là thời gian ít nhất để tới thành phố $v$, hoặc $-1$ nếu không tới được.

Ràng buộc

• $1\le n\le 3·{10}^4$
• $0\le m\le 6·{10}^4$
• $0\le k\le 3·{10}^4$
• $1\le s_j$ và $s_1+s_2+\dots +s_k\le {10}^5$
• $1\le u_i,v_i\le n$
• $1\le w_i,c_j\le {10}^9$

Ví dụ