← 返回题目列表

Codeforces · 545/E

E. 路径和树

中文机器翻译题面 查看原题

小女孩苏西无意中发现了哥哥的笔记本。她有很多事情要做,比解决问题更重要,但她发现这个问题太有趣了,所以她想知道它的解决方案,并决定向你询问。所以,问题陈述如下。

假设给定一个连通的带权无向图 G = (V, E)(这里 V 是顶点集,E 是边集)。从顶点 u 开始的最短路径树是这样的图 G1 = (V, E1),它是一棵具有边集 E1 的树,E1 是初始图 E 的边集的子集,并且从 u 到任何顶点到 G 和 G1 的最短路径长度相同。

给定一个连通的带权无向图 G 和顶点 u。你的任务是从顶点 u 找到给定图的最短路径树,其边的总权重尽可能最小。

输入

第一行包含两个数字,n 和 m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — 分别是图的顶点数和边数。

接下来的 m 行每行包含三个整数,代表一条边 — ui, vi, wi — 边连接的顶点数和边的权重 (ui ≠ vi, 1 ≤ wi ≤ 109)。保证图是连通的,并且任意一对顶点之间不存在多于一条边。

输入的最后一行包含整数 u (1 ≤ u ≤ n) — 起始顶点的编号。

输出

在第一行中打印树边缘的最小总权重。

在下一行中打印树中包含的边的索引,以空格分隔。边按照它们在输入中遵循的顺序从 1 开始编号。您可以按任何顺序打印边数。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3 3
1 2 1
2 3 1
1 3 2
3

输出 #1

2
1 2

输入 #2

4 4
1 2 1
2 3 1
3 4 1
4 1 2
4

输出 #2

4
2 3 4

注意

在第一个示例中,有两种可能的最短路径树:

- 边为 1 – 3 和 2 – 3(总权重为 3);
- 边为 1 – 2 和 2 – 3(总权重为 2);

并且,例如,具有边 1 – 2 和 1 – 3 的树不会是顶点 3 的最短路径树,因为该树中从顶点 3 到顶点 2 的距离等于 3,而在原始图中为 1。