Vũ trụ $Z$ có $n$ hành tinh, các hành tỉnh được đánh số từ $1$ đến $n$. Một hệ thống gồm $m$ đường dịch chuyển, đường dịch chuyền thứ $k\ (1\le k\le m)$ sẽ giúp di chuyền từ hành tỉnh $i_k$ đến hành tinh $j_k$ và mất chi phí là $e(i_k,j_k)$. Một vụ nổ trong vũ trụ đã làm ảnh hưởng lớn đến tất cả các hành tinh, trừ hành tinh số $1$. Hành tinh số $1$ lên kế hoạch cứu hộ cho $n-1$ hành tinh còn lại.

Các nhà khoa học ở hành tinh số 1 đã tìm ra cách di chuyển giúp đội cứu hộ có thể di chuyển đến một hành tinh khác với chi phí nhỏ hơn. Cụ thể, với số nguyên không âm $a$ mà các nhà khoa học thiết đặt, giả sử đội cứu hộ lần lượt di chuyển qua dãy gồm $p$ hành tinh $1=x_1,x_2,\dots,x_p$. Như vậy, đội cứu hộ sẽ phải sử dụng $p-1$ đường dịch chuyển, gọi $s_1$ là tổng chi phí của $p-1$ đường dịch chuyển, gọi $r_1$ là tổng chi phí của $a$ đường dịch chuyền có chi phí lớn nhất trong $p-1$ đường dịch chuyển (nếu $a>p-1$ thì tính tổng chi phí của $p-1$ đường dịch chuyển), khi đó đội cứu hộ sẽ mất chi phí là $s_1-r_1$.

Về phía các hành tinh, các nhà khoa học cũng đã tính toán ra số nguyên không âm $b$ dựa trên mức độ ảnh hưởng của vụ nồ để xác định được chi phí di chuyển của cư dân. Cụ thể, nếu cư dân hành tinh $i$ phải di chuyển qua dãy gồm $q$ hành tinh $i=y_1,y_2,\dots,y_q$, gọi $s_2$ là tổng chi phí của $q-1$ đường dịch chuyển, gọi $r_2$ là tổng chi phí của $b$ đường dịch chuyển có chi phí nhỏ nhất trong $q-1$ đường dịch chuyển (nếu $b>q-1$ thì tính tổng chi phí của $q-1$ đường dịch chuyển), khi đó cư dân sẽ mất chi phí là $s_2+r_2$.

Chi phí để đội cứu hộ gặp được cư dân của hành tinh $i$ là tổng chi phí di chuyền của đội cứu hộ cộng với tổng chi phí của cư dân hành tinh $i$ di chuyển đề họ gặp được nhau.

Yêu cầu: Với mỗi hành tinh $i\ (2\le i\le n)$, hãy tính chi phí nhỏ nhất để đội cứu hộ xuất phát từ hành tinh $1$ có thể gặp cư dân của hành tỉnh $i$.

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

0 1 2