Cây đường đi ngắn nhất nhỏ nhất

Cho một đồ thị vô hướng liên thông có trọng số $G=(V,E)$ với $n$ đỉnh và $m$ cạnh, cùng một đỉnh nguồn $u$.

Một cây đường đi ngắn nhất xuất phát từ $u$ là một cây con của $G$ (gồm đúng $n$ đỉnh và một tập con các cạnh của $G$) sao cho với mọi đỉnh $v$, khoảng cách từ $u$ đến $v$ trong cây bằng đúng khoảng cách ngắn nhất từ $u$ đến $v$ trong đồ thị ban đầu.

Trong tất cả các cây đường đi ngắn nhất xuất phát từ $u$, hãy tìm cây có tổng trọng số các cạnh nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i$, $v_i$, $w_i$: một cạnh nối hai đỉnh $u_i$ và $v_i$ với trọng số $w_i$ ($u_i\ne v_i$). Bảo đảm đồ thị liên thông và giữa hai đỉnh bất kỳ có tối đa một cạnh.
• Dòng cuối chứa số nguyên $u$: đỉnh nguồn.

Dữ liệu ra

• Dòng đầu in tổng trọng số nhỏ nhất của các cạnh trong cây.
• Dòng thứ hai in chỉ số của các cạnh thuộc cây, cách nhau bởi dấu cách. Các cạnh được đánh số từ $1$ theo thứ tự xuất hiện trong dữ liệu vào. Có thể in các chỉ số theo thứ tự bất kỳ.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le n\le 3·{10}^5$
• $0\le m\le 3·{10}^5$
• $1\le w_i\le {10}^9$
• $1\le u\le n$

Ví dụ