Đồ thị

Cho đồ thị $n$ đỉnh (đánh số từ $1$ đến $n$) và $m$ cạnh. Trọng số của mỗi cạnh là không âm. Hãy xác định đường đi ngắn nhất từ đỉnh $s$ cho trước tới mỗi đỉnh còn lại và độ dài của đường đi đó.

Mỗi cạnh $(a,b,r)$ đi được theo cả hai chiều, từ $a$ tới $b$ và từ $b$ tới $a$, với cùng trọng số $r$ (ví dụ $1$: từ đỉnh $2$ tới đỉnh $1$ đi qua cạnh "1 2 10"). Độ dài một đường đi là tổng trọng số các cạnh trên đường đi đó.

Yêu cầu: Tìm độ dài đường đi ngắn nhất từ đỉnh $s$ đến các đỉnh còn lại và truy vết đường đi cho các đỉnh được yêu cầu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($n>0$, $m\ge 0$).
• Nếu $m>0$ thì mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $a,b,r$ cho biết có cạnh nối $a$ với $b$ có trọng số $r$ ($1\le a,b\le n$, $a\ne b$, $0\le r\le {10}^6$). Không có hai dòng nào giống nhau (hai đỉnh vẫn có thể được nối bởi nhiều cạnh có trọng số khác nhau).
• Dòng thứ $m+2$ chứa số nguyên $s$ ($1\le s\le n$).
• Dòng cuối cùng chứa số nguyên $k$ và sau đó là $k$ số nguyên $c_1,c_2,\dots ,c_k$ ($1\le c_i\le n$) cho biết phải dẫn xuất đường đi ngắn nhất từ $s$ tới $c_i$, $i=1,2,\dots ,k$. Dữ liệu bảo đảm luôn có đường đi từ $s$ tới mọi $c_i$.

Dữ liệu ra

• Dòng đầu tiên chứa $n$ số nguyên, số thứ $i$ là độ dài đường đi ngắn nhất từ $s$ đến đỉnh $i$ (số thứ $s$ bằng $0$). Độ dài bằng $-1$ nếu không tồn tại đường đi từ $s$ đến đỉnh đó.
• Dòng thứ $i$ trong $k$ dòng sau chứa thông tin về đường đi ngắn nhất từ $s$ tới $c_i$, có dạng TU DINH s to ci: v1 v2 ... vt, trong đó $s$ và $c_i$ được thay bằng số hiệu đỉnh (ngay sau $c_i$ là dấu hai chấm), còn $v_1=s,v_2,\dots ,v_t=c_i$ là các đỉnh lần lượt trên đường đi, hai đỉnh liên tiếp được nối bởi một cạnh. Đường đi có không quá $n$ đỉnh và có độ dài bằng độ dài đường đi ngắn nhất từ $s$ tới $c_i$. Nếu $c_i=s$ thì đường đi chỉ gồm đỉnh $s$.

Nếu có nhiều đường đi ngắn nhất, in ra đường đi bất kỳ.

Ràng buộc

• $1\le n\le {10}^5$, $0\le m\le {10}^5$.
• $1\le a,b\le n$, $a\ne b$, $0\le r\le {10}^6$.
• $1\le s\le n$, $1\le k\le 10$, $1\le c_i\le n$, có đường đi từ $s$ tới mọi $c_i$.

Subtasks

Điểm được tính theo từng test.

• $60\%$ số test đầu tiên: $n\le {10}^3$, $m\le {10}^3$.
• $40\%$ số test còn lại: không có ràng buộc gì thêm.

Ví dụ