https://www.cnblogs.com/Gloid/p/10273902.html
这篇文章已经从头到尾讲的非常清楚了，几乎没有什么需要补充的内容。
首先$O(n\log^2 n)$的做法比较显然，倍增优化建图+最短路即可。
然后利用“每个塌陷最多会被使用一次”的性质，为每个塌陷（边也看作一种塌陷）建一个点跑一个变体的Dijkstra就可以优化到$O((n+m)\log n)$。
这里讲下我最后一步的实现。
为每个塌陷找未标记的点很简单，并查集f[i]表示离i最近的未被标记的祖先，每次标记i后f[i]=get(fa[i])即可。
为每个点找未标记的塌陷相对复杂，分两种情况考虑。
一是x是这个塌陷的LCA，这个很好处理，开个vector存储以每个点为LCA的所有塌陷即可。
二是塌陷的一个端点在x子树内，一个在子树外。
设x的子树的DFS序区间为[L,R]
考虑每次取出“一个端点在x的子树中，另一个端点的DFS序尽量小”的未标号的塌陷，若此塌陷的另一个端点在L之前则说明这个塌陷过点x。
更新完后再把这个塌陷删掉，直到取出的塌陷在L之后。同理，对“尽量大”的塌陷也做一遍，直到这个塌陷另一个端点DFS序在R之前。
于是我们要支持的是，查询一个端点在某个区间中的所有塌陷的另一个端点最小/大值。
线段树维护每个区间中的这个信息，同时在线段树的叶子上，用堆维护“以这个点为端点的所有塌陷的另一个端点”。
由于尽量小和尽量大都要做一边，所以要开一个大根堆和一个小根堆。
实现起来可能没有什么细节，只是要注意代码不要写残，自己证一遍复杂度，否则可能不小心就写成$O(n\log^2 n)$的了。
#include<queue>
#include<cstdio>
#include<algorithm>
#define ls (x<<1)
#define rs (ls|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
typedef long long ll;
using namespace std; const int N=,M=;
ll inf=1e15;
bool tag[M],b[M];
ll dis[M];
int n,m,S,u,v,w,cnt,tot,tim;
int pos[N],f[N],L[N],R[N],dep[N],fa[N][];
int h[N],to[N<<],nxt[N<<],mn[N<<],mn1[N<<],mx[N<<],mx1[N<<];
struct E{ int L1,R1,L2,R2,w; }e[M];
vector<int>ve[N]; struct P{ int id,s; };
bool operator <(const P &a,const P &b){ return a.s<b.s; }
struct Cmp{ bool operator ()(const P &a,const P &b){ return a.s>b.s; } };
priority_queue<P,vector<P>,Cmp>Q1[N];
priority_queue<P>Q2[N]; struct D{ int x; ll d; };
bool operator <(const D &a,const D &b){ return a.d>b.d; }
priority_queue<D>Q; void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
int get(int x){ return f[x]==x ? x : f[x]=get(f[x]); } void dfs(int x){
dep[x]=dep[fa[x][]]+; L[x]=++tim; pos[tim]=x;
rep(i,,) fa[x][i]=fa[fa[x][i-]][i-];
For(i,x) if ((k=to[i])!=fa[x][]) fa[k][]=x,dfs(k);
R[x]=tim;
} int Lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for (int i=; ~i; i--) if (t&(<<i)) x=fa[x][i];
if (x==y) return x;
for (int i=; ~i; i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
} void upd(int x){
if (mn1[ls]<mn1[rs]) mn[x]=mn[ls],mn1[x]=mn1[ls]; else mn[x]=mn[rs],mn1[x]=mn1[rs];
if (mx1[ls]>mx1[rs]) mx[x]=mx[ls],mx1[x]=mx1[ls]; else mx[x]=mx[rs],mx1[x]=mx1[rs];
} void build(int x,int L,int R){
if (L==R){
int p=pos[L]; mn1[x]=n+; mx1[x]=-;
if (!Q1[p].empty()) mn[x]=Q1[p].top().id,mn1[x]=Q1[p].top().s;
if (!Q2[p].empty()) mx[x]=Q2[p].top().id,mx1[x]=Q2[p].top().s;
return;
}
int mid=(L+R)>>; build(lson); build(rson); upd(x);
} void que(int x,int L,int R,int l,int r,bool k,int &s,int &s1){
if (L==l && r==R){
if (!k) s=mn[x],s1=mn1[x]; else s=mx[x],s1=mx1[x];
return;
}
int mid=(L+R)>>;
if (r<=mid) que(lson,l,r,k,s,s1);
else if (l>mid) que(rson,l,r,k,s,s1);
else{
int a,a1,b,b1;
que(lson,l,mid,k,a,a1); que(rson,mid+,r,k,b,b1);
if (!k){ if (a1<b1) s=a,s1=a1; else s=b,s1=b1; }
else { if (a1>b1) s=a,s1=a1; else s=b,s1=b1; }
}
} void del(int x,int L,int R,int p,bool k){
if (L==R){
p=pos[p];
if (!k){
Q1[p].pop(); mn[x]=; mn1[x]=n+;
if (!Q1[p].empty()) mn[x]=Q1[p].top().id,mn1[x]=Q1[p].top().s;
}else{
Q2[p].pop(); mx[x]=; mx1[x]=-;
if (!Q2[p].empty()) mx[x]=Q2[p].top().id,mx1[x]=Q2[p].top().s;
}
return;
}
int mid=(L+R)>>;
if (p<=mid) del(lson,p,k); else del(rson,p,k);
upd(x);
} void solve1(int x){
int u=e[x].L2,v=e[x].R2,lca=Lca(u,v);
u=f[u]; v=f[v];
while (dep[u]>=dep[lca] || dep[v]>=dep[lca]){
if (!u && !v) break;
if (dep[u]<dep[v]) swap(u,v);
if (!tag[u]) dis[u]=min(dis[u],dis[x+n]),Q.push((D){u,dis[u]});
tag[u]=; u=f[u]=get(fa[u][]);
}
} void solve2(int x){
int ed=ve[x].size()-;
rep(i,,ed){
int k=ve[x][i];
if (!tag[k+n]) tag[k+n]=,dis[k+n]=min(dis[k+n],dis[x]+e[k].w),Q.push((D){k+n,dis[k+n]});
}
while (){
int mn,mn1,mx,mx1;
que(,,n,L[x],R[x],,mn,mn1);
que(,,n,L[x],R[x],,mx,mx1);
if (mn1>=L[x]) mn=;
if (mx1<=R[x]) mx=;
if (!mn && !mx) break;
if (mn){
if (!tag[mn+n]) dis[mn+n]=min(dis[mn+n],dis[x]+e[mn].w),Q.push((D){mn+n,dis[mn+n]});
tag[mn+n]=; del(,,n,L[e[mn].L1]+L[e[mn].R1]-mn1,);
}
if (mx){
if (!tag[mx+n]) dis[mx+n]=min(dis[mx+n],dis[x]+e[mx].w),Q.push((D){mx+n,dis[mx+n]});
tag[mx+n]=; del(,,n,L[e[mx].L1]+L[e[mx].R1]-mx1,);
}
}
} void Dij(){
rep(i,,n+tot) dis[i]=inf; dis[S]=; Q.push((D){S,}); tag[S]=;
while (!Q.empty()){
int x=Q.top().x; Q.pop();
if (b[x]) continue;
b[x]=;
if (x>n) solve1(x-n); else solve2(x);
}
} int main(){
freopen("bzoj4699.in","r",stdin);
freopen("bzoj4699.out","w",stdout);
scanf("%d%d%d",&n,&m,&S);
rep(i,,n) scanf("%d%d%d",&u,&v,&w),e[++tot]=(E){u,u,v,v,w},e[++tot]=(E){v,v,u,u,w},add(u,v),add(v,u);
dfs();
rep(i,,n) f[i]=i;
rep(i,,m) tot++,scanf("%d%d%d%d%d",&e[tot].L2,&e[tot].R2,&e[tot].L1,&e[tot].R1,&e[tot].w);
rep(i,,tot){
int u=e[i].L1,v=e[i].R1,lca=Lca(u,v);
ve[lca].push_back(i);
Q1[u].push((P){i,L[v]}); Q2[u].push((P){i,L[v]});
Q1[v].push((P){i,L[u]}); Q2[v].push((P){i,L[u]});
}
build(,,n); Dij();
rep(i,,n) printf("%lld\n",dis[i]);
return ;
}