#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>e[4200001];
priority_queue<pair<int,int> >q;
int dis[4200001],id[4200001],vis[4200001];
int lson(int l)
{
    return l*2;
}
int rson(int l)
{
    return l*2+1;
}
void build(int rt,int l,int r,int n)
{
	e[rt+4*n].push_back(make_pair(rt,0));
	if(l==r)
	{
		id[l]=rt;
		return;
	}
	e[lson(rt)].push_back(make_pair(rt,0));
	e[rson(rt)].push_back(make_pair(rt,0));
	e[rt+4*n].push_back(make_pair(lson(rt)+4*n,0));
	e[rt+4*n].push_back(make_pair(rson(rt)+4*n,0));
	int mid=(l+r)/2;
	build(lson(rt),l,mid,n);
	build(rson(rt),mid+1,r,n);
}
void update(int rt,int l,int r,int L,int R,int pd,int n,int t)
{
	if(L<=l&&r<=R)
	{
		if(pd==0)
		{
			e[rt].push_back(make_pair(8*n+t,0));
		}
		else
		{
			e[8*n+t].push_back(make_pair(rt+4*n,pd));
		}
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid)
	{
		update(lson(rt),l,mid,L,R,pd,n,t);
	}
	if(mid<R)
	{
		update(rson(rt),mid+1,r,L,R,pd,n,t);
	}
}
void dijkstra(int s)
{
    int x,i;
	memset(dis,0x3f,sizeof(dis));
	dis[id[s]]=0;
    q.push(make_pair(0,id[s]));
	while(q.empty()==0)
	{
		x=q.top().second;
		q.pop();
		if(vis[x]==0)
		{
			vis[x]=1;
			for(i=0;i<e[x].size();i++)
			{
				if(dis[e[x][i].first]>dis[x]+e[x][i].second)
				{
					cout<<dis[x]+e[x][i].second<<endl;
					dis[e[x][i].first]=dis[x]+e[x][i].second;
					q.push(make_pair(-dis[e[x][i].first],e[x][i].first));
				}
			}
		}
	}
}
void bfs(int p)
{
	int x,i;
	memset(dis,0x3f,sizeof(dis));
    deque<int> q;
    dis[id[p]]=0;
    q.push_back(id[p]);
    while(q.empty()==0)
    {
		x=q.front();
		q.pop_front();
		for(i=0;i<e[x].size();i++)
		{
			if(dis[e[x][i].first]>dis[x]+e[x][i].second)
			{
				dis[e[x][i].first]=dis[x]+e[x][i].second;
				if(e[x][i].second==1)
				{
					q.push_back(e[x][i].first);
				}
				else
				{
					q.push_front(e[x][i].first);
				}
			}
		}
	}
}
int main()
{
    int n,m,p,t=0,i,a,b,c,d,pd,w;
    scanf("%d%d%d",&n,&m,&p);
    build(1,1,n,n);
    for(i=1;i<=m;i++)
    {
		if(pd==1)
		{
			scanf("%d%d%d",&a,&c,&w);
			b=a;
			d=c;
			t++;
			update(1,1,n,a,b,0,n,t);
			update(1,1,n,c,d,w,n,t);
		}
		if(pd==2)
		{
			scanf("%d%d%d%d",&a,&c,&d,&w);
			b=a;
			t++;
			update(1,1,n,a,b,0,n,t);
			update(1,1,n,c,d,w,n,t);
		}
		if(pd==3)
		{
			scanf("%d%d%d%d",&a,&c,&d,&w);
			b=a;
			t++;
			update(1,1,n,c,d,0,n,t);
			update(1,1,n,a,b,w,n,t);
		}
    }
    dijkstra(p);
    for(i=1;i<=n;i++)
    {
        if(i==p)
        {
            printf("0 ");
        }
        else
        {
			if(dis[id[i]+4*n]==0x3f3f3f3f)
			{
				printf("-1 ");
			}
			else
			{
				printf("%d ",dis[id[i]+4*n]);
			}
        }
    }
    return 0;
}