本地造的数据较弱，拍了十几万组没拍出来，救命。。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls rt<<1
#define rs rt<<1|1
#define mid ((l+r)>>1)
const int mx=1e6+1000;
const ll Inf=4557430888798830399;
int n,q,s,ID,len,head[mx*4];
ll dis[mx*4];
bool vis[mx*4];
struct Node{
    int to,next;
    ll data;
}e[mx<<4];
struct Tree{
    int id;
}tin[mx<<2],tout[mx<<2];
struct cmp{
    int to;
    ll data;
    bool friend operator <(cmp a,cmp b){
        return a.data>b.data;
    }
};
priority_queue <cmp> que;
void Insert(int u,int v,int w){
    e[++len].to=v;
    e[len].data=w;
    e[len].next=head[u];
    head[u]=len;
}
void Pushup(int rt){
    Insert(tin[rt].id,tin[ls].id,0);
    Insert(tin[rt].id,tin[rs].id,0);
    Insert(tout[ls].id,tout[rt].id,0);
    Insert(tout[rs].id,tout[rt].id,0);
}
void Build(int rt,int l,int r){
    if(l==r){
        tin[rt].id=l;
        tout[rt].id=r;
        return ;
    }
    Build(ls,l,mid);Build(rs,mid+1,r);
    tin[rt].id=++ID;tout[rt].id=++ID;
    Pushup(rt);
}
void updata(int rt,int l,int r,int L,int R,int from,ll w,int opt){
    if(L<=l && R>=r){
        if(opt)Insert(from,tin[rt].id,w);
        else Insert(tout[rt].id,from,w);
        return ;
    }
    if(L<=mid)updata(ls,l,mid,L,R,from,w,opt);
    if(R>mid)updata(rs,mid+1,r,L,R,from,w,opt);
}
void dij(int rt){
    memset(dis,0x3f,sizeof(dis));
    dis[rt]=0;
    que.push({rt,0});
    while(que.empty()==false){
        int u=que.top().to;que.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].data){
                dis[v]=dis[u]+e[i].data;
                que.push({v,dis[v]});
            }
        }
    }
}
void MYH(){
    scanf("%d%d%d",&n,&q,&s);
    int opt,u,v,l,r,w;ID=n;
    Build(1,1,n);
    for(int i=1;i<=q;++i){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&u,&v,&w);
            Insert(u,v,w);
        }
        if(opt==2){
            scanf("%d%d%d%d",&v,&l,&r,&w);
            updata(1,1,n,l,r,v,w,1);
        }
        if(opt==3){
            scanf("%d%d%d%d",&v,&l,&r,&w);
            updata(1,1,n,l,r,v,w,0);
        }
    }
    dij(s);
    for(int i=1;i<=n;++i){
        if(dis[i]==Inf)printf("-1 ");
        else printf("%lld ",dis[i]);
    }
}
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    MYH();
    return 0;
}