原题传送门
题意神奇，反正我是理解了好长的时间
差不多就是求一个生成树，使得任意点到源点的最短路等于原图中的最短路
再让这个生成树边权和最小

很显然得先dij一下
考虑dij过程中松弛的条件，跟一般的dij不一样，为了满足本题的要求，还要生成树边权最小
自然是两点间路程相等情况下，经过的边数越多越好（感性理解一下）

最短路跑出之后如何得知建出来的生成树？
简单，对于每个点开一个$pre$pre数组表示父亲连到自己的边的编号
然后可以通过这个解决题目交给我们的任务

Code：

#include <bits/stdc++.h>
#define maxn 300010
#define inf 1e18
#define int long long
using namespace std;
struct node{
	int val, len;
	bool operator < (const node &x) const{ return x.len < len; }
};
priority_queue <node> q;
struct Edge{
	int to, next, len;
}edge[maxn << 1];
int num, head[maxn], n, m, rt, vis[maxn], dis[maxn], pre[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge) { y, head[x], z }; head[x] = num; }

signed main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read(), z = read();
		addedge(x, y, z); addedge(y, x, z);
	}
	rt = read();
	for (int i = 1; i <= n; ++i) dis[i] = inf; dis[rt] = 0;
	q.push((node) {rt, 0});
	while (!q.empty()){
		node tmp = q.top(); q.pop();
		int u = tmp.val, len = tmp.len;
		if (vis[u]) continue; vis[u] = 1;
		for (int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			if (dis[v] >= len + edge[i].len){//不一样的松弛条件，注意这个等号
				dis[v] = len + edge[i].len, pre[v] = i;
				if (!vis[v]) q.push((node) {v, dis[v]});
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) if (i != rt) ans += edge[pre[i]].len;
	printf("%lld\n", ans);
	for (int i = 1; i <= n; ++i) if (i != rt)  printf("%lld ", (pre[i] + 1) >> 1);
	return 0;
}