给定一幅无向带权连通图G = (V, E) (这里V是点集，E是边集)。从点u开始的最短路径树是这样一幅图G1 = (V, E1)，其中E1是E的子集，并且在G1中，u到所有其它点的最短路径与他在G中是一样的。
现在给定一幅无向带权连通图G和一个点u。你的任务是找出从u开始的最短路径树，并且这个树中所有边的权值之和要最小。
Input
第一行有两个整数n和m(1 ≤ n ≤ 3*10^5, 0 ≤ m ≤ 3*10^5)，表示点和边的数目。
接下来m行，每行包含3个整数 ui, vi, wi ，表示ui和vi之间有一条权值为wi的无向边(1 ≤ ui,vi ≤ n, 1 ≤ wi ≤ 10^9)。
输入保证图是连通的。
最后一行给出一个整数u (1 ≤ u ≤ n)，表示起点。
Output
输出这棵树的最小的权值之和。
不能直接求完最短路图后跑MST。。因为最短路图的边都是有向的。答案应该是最短路图里每个点最小的前驱边之和。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define ll long long
#define ui unsigned int
#define ull unsigned long long
using namespace std;
const int maxn=;
struct zs{int too,pre,dis;}e[maxn<<];int tot,last[maxn];
int dl[],pre[maxn];
ll dis[maxn],ans;
int i,j,k,n,m;
bool u[maxn]; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
} inline void insert(int a,int b,int c){
e[++tot].too=b,e[tot].dis=c,e[tot].pre=last[a],last[a]=tot,
e[++tot].too=a,e[tot].dis=c,e[tot].pre=last[b],last[b]=tot;
}
inline void spfa(int s){
memset(dis+,,n<<);
int l=,r=,i,now,to;dl[]=s,dis[s]=;
while(l<r)for(now=dl[++l],u[now]=,i=last[now];i;i=e[i].pre)
if(dis[to=e[i].too]>dis[now]+e[i].dis){
dis[to]=dis[now]+e[i].dis,pre[to]=e[i].dis;
if(!u[to])dl[++r]=to,u[to]=;
}else if(dis[to]==dis[now]+e[i].dis&&e[i].dis<pre[to])pre[to]=e[i].dis;
}
int main(){
n=read(),m=read();
for(i=;i<=m;i++)j=read(),k=read(),insert(j,k,read());
int s=read();spfa(s);
for(i=;i<=n;i++)ans+=pre[i];
printf("%lld\n",ans);
}