```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define push_back emplace_back
#define ull unsigned long long
#define pii pair<long long,int>
/*
* theFileCreatedAt_2022-07-09_13:21_ *
* 只有结束的时候才会结束
*/
ll read(){
ll w=1,q=0;
char ch=' ';
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') q=(ll)q*10+ch-'0',ch=getchar();
return (ll)w*q;
}
const int maxn=1e5+19;
struct xqx{
struct{
int nxt,to;
long long dis;
}mp[maxn*40];
int now=0,head[maxn*40];
inline void addedge(int u,int v,long long dis){
mp[++now].to=v;
mp[now].nxt=head[u];
mp[now].dis=dis;
head[u]=now;
}
}mp;
int n;
int now;
struct SegTree{
struct{
int l,r;
int id;
}st[maxn*4];
int type=0;
void build(int rt,int l,int r){
st[rt].l=l,st[rt].r=r;
if(l==r){
st[rt].id=l;
return;
}
st[rt].id=++now;
int m=(l+r)/2;
build(rt*2,l,m);
build(rt*2+1,m+1,r);
if(type==0){
mp.addedge(st[rt].id,st[rt*2].id,0);
mp.addedge(st[rt].id,st[rt*2+1].id,0);
}
else{
mp.addedge(st[rt*2].id,st[rt].id,0);
mp.addedge(st[rt*2+1].id,st[rt].id,0);
}
}
void addedge(int rt,int tgt,int s,int e,long long w){
int l=st[rt].l,r=st[rt].r;
if(s<=l&&r<=e){
if(type==0) mp.addedge(tgt,st[rt].id,w);
else mp.addedge(st[rt].id,tgt,w);
return;
}
if(e<l||r<s) return;
addedge(rt*2,tgt,s,e,w);
addedge(rt*2+1,tgt,s,e,w);
}
}st1,st2;
long long dis[maxn*40];
int vis[maxn*40];
priority_queue<pii,vector<pii>,greater<pii>>pq;
const long long inf=1e18;
void dijk(int start,int size){
for(int i=1;i<=size;i++)dis[i]=inf;
for(int i=1;i<=size;i++)vis[i]=0;
dis[start]=0;
pq.push(pii(0,start));
while(!pq.empty()){
int it=pq.top().second;
pq.pop();
if(vis[it])continue;
vis[it]=1;
for(int i=mp.head[it];i;i=mp.mp[i].nxt){
long long di=mp.mp[i].dis;
int id=mp.mp[i].to;
if(dis[id]>dis[it]+di){
dis[id]=dis[it]+di;
pq.push(pii(dis[id],id));
}
}
}
}
void solve(){
int q,s;
cin>>n>>q>>s;
now=n;
int t;
int u,v,l,r;
long long w;
st2.type=1;
st1.build(1,1,n);
st2.build(1,1,n);
for(int i=1;i<=q;i++){
cin>>t;
if(t==1){
cin>>v>>u>>w;
mp.addedge(v,u,w);
}
else if(t==2){
//v->[l,r]
cin>>v>>l>>r>>w;
st1.addedge(1,v,l,r,w);
}
else{
//[l,r]->v
cin>>v>>l>>r>>w;
st2.addedge(1,v,l,r,w);
}
}
dijk(s,now);
/*
for(int i=1;i<=now;i++){
cout<<i<<':';
for(int j=mp.head[i];j;j=mp.mp[j].nxt)cout<<mp.mp[j].to<<'#'<<mp.mp[j].dis<<' ';
cout<<endl;
}
*/
for(int i=1;i<=n;i++)cout<<(dis[i]==inf?-1:dis[i])<<' ';
cout<<endl;
}
int main(){
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
#endif
int t;
t=1;
while(t--){
solve();
}
return 0;
}
```
by paradoxxd @ 2022-07-12 10:23:01