CF545E.Paths and Trees

Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows.

Let's assume that we are given a connected weighted undirected graph G = (V, E) (here V is the set of vertices, E is the set of edges). The shortest-path tree from vertex u is such graph _G_1 = (V, _E_1) that is a tree with the set of edges _E_1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to _G_1 are the same.

You are given a connected weighted undirected graph G and vertex u. Your task is to find the shortest-path tree of the given graph from vertex u, the total weight of whose edges is minimum possible.

小女孩苏西偶然发现了她哥哥的笔记本。她有很多事情要做，而且这些事都比解题更重要；但她觉得这个问题实在太有趣了，因此很想了解它的解法，并决定向你请教。问题描述如下：

假设我们给定一个连通的带权无向图 $G = (V, E)$（其中 $V$ 是顶点集，$E$ 是边集）。从顶点 $u$ 出发的最短路径树是指这样一个图 $G_1 = (V, E_1)$：它是一棵树，其边集 $E_1$ 是原图边集 $E$ 的子集，且对任意顶点 $v$，从 $u$ 到 $v$ 在 $G$ 中的最短路径长度与在 $G_1$ 中的最短路径长度相等。

现给你一个连通的带权无向图 $G$ 和一个顶点 $u$。你的任务是找出图 $G$ 中以 $u$ 为根的最短路径树，且要求该树所有边的总权重尽可能小。

The first line contains two numbers, n and m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of vertices and edges of the graph, respectively.

Next m lines contain three integers each, representing an edge — u__i, v__i, w__i — the numbers of vertices connected by an edge and the weight of the edge (u__i ≠ v__i, 1 ≤ w__i ≤ 109). It is guaranteed that graph is connected and that there is no more than one edge between any pair of vertices.

The last line of the input contains integer u (1 ≤ u ≤ n) — the number of the start vertex.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 3 \cdot 10^5$，$0 \leq m \leq 3 \cdot 10^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$）—— 起始顶点的编号。

In the first line print the minimum total weight of the edges of the tree.

In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from 1 in the order they follow in the input. You may print the numbers of the edges in any order.

If there are multiple answers, print any of them.

第一行输出该树的边的总权重的最小值。

第二行输出构成该树的边的编号，各编号之间用空格分隔。边的编号从 1 开始，按照输入中出现的顺序依次编号。边的编号可以以任意顺序输出。

若存在多个答案，输出其中任意一个即可。

In the first sample there are two possible shortest path trees:

• with edges 1 – 3 and 2 – 3 (the total weight is 3);
• with edges 1 – 2 and 2 – 3 (the total weight is 2);

And, for example, a tree with edges 1 – 2 and 1 – 3 won't be a shortest path tree for vertex 3, because the distance from vertex 3 to vertex 2 in this tree equals 3, and in the original graph it is 1.

在第一个样例中，存在两种可能的最短路径树：

• 包含边 $1\,–\,3$ 和 $2\,–\,3$（总权重为 $3$）；
• 包含边 $1\,–\,2$ 和 $2\,–\,3$（总权重为 $2$）；

例如，包含边 $1\,–\,2$ 和 $1\,–\,3$ 的树不是顶点 $3$ 的最短路径树，因为在此树中顶点 $3$ 到顶点 $2$ 的距离为 $3$，而在原图中该距离为 $1$。