rt,是建图问题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls rt<<1
#define rs rt<<1|1
#define int ll
const int inf=1e18;
const int N=1e5+7;
int n,q,s,dis[N<<4],vis[N<<4],lf1[N],lf2[N],tot=0;
struct tree{int l,r;}t1[N<<3],t2[N<<3];
struct edge{int to,dis;};
vector<edge>e[N<<4];
inline void build1(int l,int r,int rt){
	if(l>r)return;
	t1[rt].l=l,t1[rt].r=r;
	if(l==r){
		lf1[l]=rt;
		return;
	}
	int mid=(t1[rt].l+t1[rt].r)>>1;
	build1(l,mid,ls);
	build1(mid+1,r,rs);
	e[rt].push_back({ls,0});
	e[rt].push_back({rs,0});
}
inline void build2(int l,int r,int rt){
	if(l>r)return;
	t2[rt].l=l,t2[rt].r=r;
	if(l==r){
		lf2[l]=rt+tot;
		e[lf1[l]].push_back({lf2[l],0});
		e[lf2[l]].push_back({lf1[l],0});
		return;
	}
	int mid=(t2[rt].l+t2[rt].r)>>1;
	build2(l,mid,ls);
	build2(mid+1,r,rs);
	e[ls+tot].push_back({rt+tot,0});
	e[rs+tot].push_back({rt+tot,0});
}
inline void add1(int l,int r,int rt,int from,int x){
	if(t1[rt].l>=l&&t1[rt].r<=r){
		e[from].push_back({rt,x});
		return;
	}
	int mid=(t1[rt].l+t1[rt].r)>>1;
	if(mid>=l)add1(l,r,ls,from,x);
	if(mid<r)add1(l,r,rs,from,x);
}
inline void add2(int l,int r,int rt,int to,int x){
	if(t2[rt].l>=l&&t2[rt].r<=r){
		e[rt+tot].push_back({to,x});
		return;
	}
	int mid=(t2[rt].l+t2[rt].r)>>1;
	if(mid>=l)add2(l,r,ls,to,x);
	if(mid<r)add2(l,r,rs,to,x);
}
inline void Dij(int s){
	for(int i=0;i<N;i++)dis[i]=inf;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q; 
	dis[lf2[s]]=0;
	q.push({0,lf2[s]});
	while(!q.empty()){
		int u=q.top().second;q.pop();	
		if(vis[u])continue;
		vis[u]=1;
		for(auto x:e[u]){
			int v=x.to,w=x.dis;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
}
signed main(){
	cin>>n>>q>>s;
	build1(1,n,1);
	tot=(n<<2);
	build2(1,n,1);
	while(q--){
		int op;cin>>op;
		if(op==1){
			int u,v,w;cin>>u>>v>>w;
			e[lf2[u]].push_back({lf1[v],w});
		}else if(op==2){
			int u,l,r,w;cin>>u>>l>>r>>w;
			add1(l,r,1,lf2[u],w);
		}else{
			int u,l,r,w;cin>>u>>l>>r>>w;
			add2(l,r,1,lf1[u],w);
		}
	}
	Dij(s);
	for(int i=1;i<=n;i++){
		if(dis[lf1[i]]==inf)cout<<-1<<" ";
		else cout<<dis[lf1[i]]<<" ";
	}
}