Description：

给一张带权无向图，求一棵边权之和最小的树，使得从起点到每个点的树上距离等于图上的最短路。

$1\leqslant n,m\leqslant 3\times 10^5$

Solution：

发现让求的就是一棵最短路树，但是要求边权最小，一个可以的做法是把最短路图建出来之后跑 $kruskal$ ，但是这样最短路图不好建。

除了 $kruskal$ 和 $prim$ 之外最小生成树还有一种算法叫做 $Boruvka$ ，大概就是每次为一个联通块找一条边权最小的出边，这个可以用类似的做法，因为最短路图是一个 $DAG$ ，那么就可以按拓扑顺序为每个点选父亲，即在他之前的点最短路树已建好，考虑把他加进去，但并不用把最短路图建出来，只要为每个点找一个入边权最小的父亲就行了，这个可以在 $dijkstra$ 时动态维护。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

int s;

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

typedef long long ll;

ll d[MAXN];

int fa[MAXN],l[MAXN];

bool v[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	scanf("%d",&s);

	priority_queue< pair<ll,int> > q;

	memset(d,0x3f,sizeof(d));d[s] = 0;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				l[e[i].to] = 0x3f3f3f3f;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

			if(d[e[i].to] == d[k] + e[i].v && e[i].v < l[e[i].to])

			{

				fa[e[i].to] = k;l[e[i].to] = e[i].v;

			}

		}

	}

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		if(i != s)

		{

			ans += l[i];

		}

	}

	cout << ans << endl;

	return 0;

}