Cứu hộ

Vũ trụ Z có $n$ hành tinh, các hành tinh đượ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 tinh $i_k$ đến hành tinh $j_k$ (chỉ theo một chiều) 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$.

Trong các dãy hành tinh trên, mỗi bước đi từ $x_t$ đến $x_{t+1}$ (hoặc từ $y_t$ đến $y_{t+1}$) phải theo một đường dịch chuyển từ $x_t$ đến $x_{t+1}$; một hành tinh hay một đường dịch chuyển có thể được đi qua nhiều lần, khi đó chi phí của đường dịch chuyển được tính mỗi lần sử dụng. Dãy có thể chỉ gồm một hành tinh ($p=1$ hoặc $q=1$, không di chuyển), khi đó chi phí bằng $0$.

Chi phí để đội cứu hộ gặp được cư dân 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 (tại cùng một hành tinh).

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 hành tinh $i$.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $n,m,a,b$;
• Dòng thứ $k$ ($1\le k\le m$) trong $m$ dòng tiếp theo chứa ba số nguyên dương $i_k,j_k,e(i_k,j_k)$, trong đó $1\le i_k\ne j_k\le n$ và $e(i_k,j_k)\le {10}^9$. Dữ liệu đảm bảo từ hành tinh $i$ không có quá một đường dịch chuyển tới $j$ và không tới chính nó.

Dữ liệu ra

In ra một dòng gồm $n-1$ số, số thứ $i$ là chi phí nhỏ nhất để đội cứu hộ có thể gặp cư dân hành tinh $i+1$, nếu đội cứu hộ không thể gặp được cư dân thì đưa ra số $-1$ tương ứng.

Ràng buộc

• $2\le n\le {10}^5$; $1\le m\le {10}^5$;
• $0\le a,b\le 3$;
• $1\le i_k\ne j_k\le n$; $1\le e(i_k,j_k)\le {10}^9$.

Subtasks

• Subtask 1 ($25\%$ số điểm): $n\le 100$; $m\le 1000$; $a=b=0$;
• Subtask 2 ($25\%$ số điểm): $n\le 100$; $m\le 1000$; $a=b=1$;
• Subtask 3 ($25\%$ số điểm): $n\le {10}^5$; $m\le {10}^5$; $a=b=0$;
• Subtask 4 ($25\%$ số điểm): $n\le {10}^5$; $m\le {10}^5$; $0\le a,b\le 3$.

Ví dụ