Lộ trình ngắn nhất

Cho một đồ thị vô hướng gồm $n$ đỉnh đánh số từ $1$ đến $n$ và $m$ cạnh, cùng hai đỉnh $s$ và $t$. Cạnh thứ $i$ nối hai đỉnh $u_i$, $v_i$ và có độ dài $w_i$. Đồ thị có thể có khuyên và nhiều cạnh nối cùng một cặp đỉnh.

Hãy tìm một đường đi từ $s$ tới $t$ có tổng độ dài nhỏ nhất và in ra đường đi đó. Nếu có nhiều đường đi ngắn nhất, in ra đường nào cũng được. Nếu $s=t$, đường đi ngắn nhất chỉ gồm đúng một đỉnh $s$ và có độ dài $0$.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên $n$, $m$, $s$, $t$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $u_i,v_i,w_i$.

Dữ liệu ra

• Nếu không có đường đi từ $s$ tới $t$, in ra một số $-1$.
• Ngược lại, dòng thứ nhất in ra hai số $d$ và $k$: $d$ là độ dài đường đi ngắn nhất, $k$ là số đỉnh trên đường đi bạn chọn. Dòng thứ hai in ra $k$ đỉnh của đường đi theo thứ tự từ $s$ tới $t$, cách nhau bởi một dấu cách.

Ràng buộc

• $1\le n\le 5·{10}^4$
• $0\le m\le {10}^5$
• $1\le s,t,u_i,v_i\le n$
• $1\le w_i\le {10}^9$

Ví dụ