CF545E Paths and Trees

小女孩 Susie 偶然发现了她哥哥的笔记本。她有很多事情要做，比解题更重要，但她发现这道题非常有趣，所以她想知道它的答案并决定向你请教。因此，题目的描述如下： 假设给定一个连通的带权无向图 $G=(V,E)$（其中 $V$ 是顶点集，$E$ 是边集）。从顶点 $u$ 出发的最短路树是指这样一个图 $G_{1}=(V,E_{1})$，其中 $E_{1}$ 是初始边集 $E$ 的子集，且 $G_1$ 是一棵树，并且从 $u$ 到任意顶点的最短路径在 $G$ 和 $G_1$ 中长度相同。 你被给定一个连通的带权无向图 $G$ 和顶点 $u$。你的任务是找到一棵以 $u$ 为根、边权和尽可能小的最短路树。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 3\times10^{5}$，$0 \leq m \leq 3\times10^{5}$），表示图中顶点和边的数量。 接下来的 $m$ 行，每行包含三个整数，表示一条边——$u_i, v_i, w_i$——分别为这条边连接的两个顶点以及这条边的权值（$u_i \neq v_i, 1 \leq w_i \leq 10^9$）。保证图是连通的，且任意一对顶点间最多只有一条边。 输入的最后一行包含一个整数 $u$（$1\leq u\leq n$），表示起始顶点的编号。

第一行输出该树所有边的最小总权值。 第二行输出构成这棵树的各条边的编号，编号从输入顺序的 $1$ 开始，按任意顺序输出多个编号，每个编号之间用空格隔开。 如果存在多组答案，输出其中任意一组均可。

在第一个样例中，存在两种可能的最短路树： - 选边 $1-3$ 和 $2-3$（总权值为 $3$）； - 选边 $1-2$ 和 $2-3$（总权值为 $2$）； 例如，选边 $1-2$ 和 $1-3$ 的树并不是以 $3$ 为根的最短路树，因为此时从顶点 $3$ 到顶点 $2$ 的距离是 $3$，而在原图中的最短距离是 $1$。 由 ChatGPT 5 翻译