首先一般化的将下水道和塌陷看成一个东西。注意到在从源点出发的所有需要使用某条下水道的最短路径中，该下水道只会被使用一次，该下水道第一个被访问的点相同，且只会在第一个访问的点使用该下水道。这个第一个访问的点显然就是正常dij过程中，该下水道第一个被取出的点。
于是在dij过程中，取出了某个点进行更新后，就可以将所有起点包含它的边删掉了。但这样仍然没有复杂度保证，因为一条下水道会带来很多需要更新的点，且每个点会被重复更新多次。
那么可以想到稍微魔改一下dij，将点和下水道均入堆，其中下水道的权值是其第一个被访问的点的最短路+边权。如果某次从堆中取出的是下水道，使用其更新所有还未被取出的点，这样这条下水道已经发挥了所有功能可以被删掉，而所有其更新的点的最短路一定已被其确定，不需要再次更新，可以打上标记；如果从堆中取出的是点，使用其更新所有还未被使用的下水道即可，同理可以将该点删掉且下水道权值不会被再次更新。
最后的问题是如何实现这一过程。冷静一下，我们需要的操作只是找到一条下水道所连的所有未被标记的点、一个点所连的所有未被标记的下水道。前一个问题比较简单，可以在树上弄个并查集，维护其到根的路径上的第一个未被标记的点，查询时求个lca即可。后一个问题可以考虑枚举该点每棵子树，查询是否存在一端在该子树内一端在该子树外的路径，这可以用线段树维护一下dfs序区间的路径端点dfs序min和max，叶子处维护堆即可（或许用multiset会好写很多）。注意特殊处理一下一端恰为该节点的路径。
好像7k代码刷新了我的记录了啊？又丑又长还跑的慢。
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 250010
#define M 600010
#define ll long long
int n,m,S,fa[N];
ll d[N];
struct road{int l1,r1,l2,r2,c;
}a[M];
struct data
{
int x,op;ll d;
bool operator <(const data&a) const
{
return d>a.d;
}
};
priority_queue<data> q;
vector<int> id;
namespace segment_tree
{
struct data1
{
int x,i;
bool operator <(const data1&a) const
{
return x<a.x||x==a.x&&i<a.i;
}
bool operator ==(const data1&a) const
{
return x==a.x&&i==a.i;
}
};
struct data2
{
int x,i;
bool operator <(const data2&a) const
{
return x>a.x||x==a.x&&i>a.i;
}
bool operator ==(const data2&a) const
{
return x==a.x&&i==a.i;
}
};
struct node
{
int L,R;data1 min;data2 max;
priority_queue<data2> ins_min,del_min;
priority_queue<data1> ins_max,del_max;
void update()
{
while (!del_min.empty()&&ins_min.top()==del_min.top()) ins_min.pop(),del_min.pop();
while (!del_max.empty()&&ins_max.top()==del_max.top()) ins_max.pop(),del_max.pop();
min=(data1){ins_min.top().x,ins_min.top().i};
max=(data2){ins_max.top().x,ins_max.top().i};
}
void ins(int x,int i){ins_min.push((data2){x,i}),ins_max.push((data1){x,i}),update();}
void del(int x,int i){del_min.push((data2){x,i}),del_max.push((data1){x,i}),update();}
}tree[N<<];
void up(int k){tree[k].min=min(tree[k<<].min,tree[k<<|].min),tree[k].max=min(tree[k<<].max,tree[k<<|].max);}
void build(int k,int l,int r)
{
tree[k].L=l,tree[k].R=r;
tree[k].min=(data1){N,},tree[k].max=(data2){,};
if (l==r)
{
tree[k].ins_min.push((data2){N,}),
tree[k].ins_max.push((data1){,});
return;
}
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
}
data1 query_min(int k,int l,int r)
{
if (tree[k].L==l&&tree[k].R==r) return tree[k].min;
int mid=tree[k].L+tree[k].R>>;
if (r<=mid) return query_min(k<<,l,r);
else if (l>mid) return query_min(k<<|,l,r);
else return min(query_min(k<<,l,mid),query_min(k<<|,mid+,r));
}
data2 query_max(int k,int l,int r)
{
if (tree[k].L==l&&tree[k].R==r) return tree[k].max;
int mid=tree[k].L+tree[k].R>>;
if (r<=mid) return query_max(k<<,l,r);
else if (l>mid) return query_max(k<<|,l,r);
else return min(query_max(k<<,l,mid),query_max(k<<|,mid+,r));
}
void ins(int k,int p,int x,int i)
{
if (tree[k].L==tree[k].R) {tree[k].ins(x,i);return;}
int mid=tree[k].L+tree[k].R>>;
if (p<=mid) ins(k<<,p,x,i);
else ins(k<<|,p,x,i);
up(k);
}
void del(int k,int p,int x,int i)
{
if (tree[k].L==tree[k].R) {tree[k].del(x,i);return;}
int mid=tree[k].L+tree[k].R>>;
if (p<=mid) del(k<<,p,x,i);
else del(k<<|,p,x,i);
up(k);
}
}
using segment_tree::query_min;
using segment_tree::query_max;
using segment_tree::ins;
using segment_tree::del;
namespace tree
{
int p[N],t,fa[N][],deep[N],dfn[N],size[N],cnt;
struct data{int to,nxt;}edge[N<<];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{
size[k]=;dfn[k]=++cnt;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k][])
{
fa[edge[i].to][]=k;
deep[edge[i].to]=deep[k]+;
dfs(edge[i].to);
size[k]+=size[edge[i].to];
}
}
void build()
{
fa[][]=;deep[]=;dfs();
for (int j=;j<;j++)
for (int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
}
int lca(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
for (int j=;~j;j--) if (deep[fa[x][j]]>=deep[y]) x=fa[x][j];
if (x==y) return x;
for (int j=;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
return fa[x][];
}
int getfa(int k){return k==?:fa[k][];}
bool in(int x,int l,int r){return dfn[x]<l||dfn[x]>r;}
bool cross(int x,int l,int r){return in(a[x].l1,l,r)&&!in(a[x].r1,l,r)||in(a[x].r1,l,r)&&!in(a[x].l1,l,r);}
void push(int l,int r)
{
for (;;)
{
int u=query_min(,l,r).i;
if (cross(u,l,r)) id.push_back(u),del(,dfn[a[u].l1],dfn[a[u].r1],u),del(,dfn[a[u].r1],dfn[a[u].l1],u);
else break;
}
for (;;)
{
int u=query_max(,l,r).i;
if (cross(u,l,r)) id.push_back(u),del(,dfn[a[u].l1],dfn[a[u].r1],u),del(,dfn[a[u].r1],dfn[a[u].l1],u);
else break;
}
}
void get(int k)
{
id.clear();
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k][])
{
int x=edge[i].to,l=dfn[x],r=dfn[x]+size[x]-;
push(l,r);
}
for (;;)
{
int u=query_min(,dfn[k],dfn[k]).i;
if (u) id.push_back(u),del(,dfn[a[u].l1],dfn[a[u].r1],u),del(,dfn[a[u].r1],dfn[a[u].l1],u);
else break;
}
}
}
using tree::deep;
using tree::getfa;
using tree::dfn;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dijkstra()
{
q.push((data){S,,});
memset(d,,sizeof(d));
for (int i=;i<=n;i++) fa[i]=i;fa[S]=find(getfa(S));
while (!q.empty())
{
data x=q.top();q.pop();
if (x.op==)
{
d[x.x]=x.d;tree::get(x.x);
for (int i=;i<id.size();i++)
q.push((data){id[i],,x.d+a[id[i]].c});
}
else
{
int u=a[x.x].l2,v=a[x.x].r2,w=tree::lca(u,v);
for (u=find(u);deep[u]>=deep[w];u=find(u))
q.push((data){u,,x.d}),fa[u]=find(getfa(u));
for (v=find(v);deep[v]>=deep[w];v=find(v))
q.push((data){v,,x.d}),fa[v]=find(getfa(v));
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4699.in","r",stdin);
freopen("bzoj4699.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read(),S=read();
for (int i=;i<n;i++)
{
int x=read(),y=read(),z=read();
tree::addedge(x,y),tree::addedge(y,x);
m++,a[m].l1=a[m].r1=x,a[m].l2=a[m].r2=y,a[m].c=z;
m++,a[m].l1=a[m].r1=y,a[m].l2=a[m].r2=x,a[m].c=z;
}
for (int i=;i<=m-(n-)*;i++) a[i].l2=read(),a[i].r2=read(),a[i].l1=read(),a[i].r1=read(),a[i].c=read();
tree::build();segment_tree::build(,,n);
for (int i=;i<=m;i++)
ins(,dfn[a[i].l1],dfn[a[i].r1],i),
ins(,dfn[a[i].r1],dfn[a[i].l1],i);
dijkstra();
for (int i=;i<=n;i++) printf(LL,d[i]);
return ;
}