挺好的一个题，线段树建图+拆点+最短路。

这个题一眼看上去感觉不就是对于每个条件，对于区间[l,r]的所有点都连上一条边，完了在跑个最短路就完事儿了。

但是看见数据范围的时候就傻眼了，因为最坏情况每一次会有O(n)个点相关，因此，边的数目都会最坏达到O(N*N)无法接受。

那么，对于1e5左右的数据范围，其实很容易联想到O（NlogN）的做法，既然N*N会超时，不如试试能不能有NlogN的做法？

如果能想到线段树就好做了！线段树是对于区间的修改查询的利器，可以把上述的操作转换为，每一次对于一个区间和一个点连边，那么对于一个区间，线段树是可以做到logN的时间复杂度的，所以最多有N*logN条边，N1e5,NlogN不超过2e6 这个范围是可以接受的。

还有一个要点是联想到网络流的拆点技巧，对于每一个点（包括线段树的结点），拆成入点出点，连边。

最后就是求个最短路了，我用的是spfa，不知道dijkstra能不能过（应该也可以，但是我没试）。

CODE:

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.text","r",stdin)
#define pi acos(-1)
const int mo=1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
ll qp(ll a,ll b){if(a==0) return 0;ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;}
template<class T> bool read(T & ret)//ll,int,double,float,+/-
{
    char c;int sgn;T bit=0.1;if(c=getchar(),c==EOF) return 0;while(c!='-' && c!='.' && (c<'0' || c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0' && c<='9') ret=ret*10+(c-'0');if(c==' '||c=='\n') {ret*=sgn;return 1;}while(c=getchar(),c>='0' && c<='9') ret+=(c-'0')*bit,bit/=10;ret*=sgn;return 1;
}

int n,q,s;

const int N=100010,M=N*20;
int idx;
int h[M],e[M],f[M],ne[M],w[M];
ll d[M];
int id;
struct Node{
    int l,r,idx;
}tr[2][N<<2];

map<int,int> mmp[2];
void add(int a,int b,int c)
{
    e[id] = b,w[id]=c,ne[id]=h[a],h[a]=id++;
}

void add_(int now,int a,int b,int c)
{
    a=tr[now][a].idx;
    b=tr[now][b].idx;
    e[id] = b,w[id]=c,ne[id]=h[a],h[a]=id++;

}
void build(int now,int u,int l,int r)
{
    tr[now][u] = {l,r,++idx};
    if(l==r) {
        mmp[now][l]=idx;
        return ;
    }
    int mid=l+r>>1;

    build(now,u<<1,l,mid);
    build(now,u<<1|1,mid+1,r);
    if(now==0)add_(0,u,u<<1,0),add_(0,u,u<<1|1,0);//ru
    else add_(1,u<<1|1,u,0),add_(1,u<<1,u,0);//chu
}

void add1(int v,int u,int l,int r,int w)
{
    if(tr[0][u].l>=l&&tr[0][u].r<=r) {add(mmp[1][v],tr[0][u].idx,w);return ;}
    int mid=tr[0][u].l+tr[0][u].r>>1;
    if(l<=mid) add1(v,u<<1,l,r,w);
    if(r>mid) add1(v,u<<1|1,l,r,w);
}

void add2(int v,int u,int l,int r,int w)
{
    if(tr[1][u].l>=l&&tr[1][u].r<=r) {add(tr[1][u].idx,mmp[0][v],w);return ;}
    int mid=tr[1][u].l+tr[1][u].r>>1;
    if(l<=mid) add2(v,u<<1,l,r,w);
    if(r>mid) add2(v,u<<1|1,l,r,w);
}


bool st[M];
void spfa()
{
    queue<int> q;
    s=mmp[1][s];
    q.push(s);
    memset(d,0x3f,sizeof d);
    d[s]=0;
    while(q.size())
    {
        int t=q.front();
//        cout<<"spfa"<<t<<endl;
        q.pop();
        st[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]>d[t]+w[i])
            {
                d[ver]=d[t]+w[i];
                if(!st[ver])
                {
                    st[ver]=true;
                    q.push(ver);
                }
            }
        }
    }
}

void gao()
{
    for(int i=1;i<=n;++i)
    {
        add(mmp[0][i],mmp[1][i],0);
    }
}
signed main(){
    memset(h,-1,sizeof h);

    cin>>n>>q>>s;
    build(0,1,1,n);
    build(1,1,1,n);
    while(q--)
    {
        int op;
        cin>>op;
        int l,r,v,u,w;
        if(op==1)
        {
            cin>>u>>v>>w;
            add(mmp[1][u],mmp[0][v],w);
        }
        else if(op==2)
        {
            cin>>v>>l>>r>>w;
            add1(v,1,l,r,w);
        }
        else {
            cin>>v>>l>>r>>w;
            add2(v,1,l,r,w);
        }
    }
    gao(); 
    spfa();
    for(int i=1;i<=n;++i) if(d[mmp[1][i]]>1e18) cout<<"-1 ";else cout<<d[mmp[1][i]]<<' ';
    return 0;
}