小女孩苏西无意中发现了哥哥的笔记本。她有很多事情要做,比解决问题更重要,但她发现这个问题太有趣了,所以她想知道它的解决方案,并决定向你询问。所以,问题陈述如下。
假设给定一个连通的带权无向图 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。