#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
#include<map>
#include<set>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include<bitset>
using namespace std;
const int N=100005;
int n,m,s;
struct nod{
	int l,r;
}tree[N<<2],tree2[N<<2];
int zhuan[N];
void dfs(int ro,int l,int r){
	tree[ro].l=l;tree[ro].r=r;
	tree2[ro].l=l;tree2[ro].r=r;
	if(l==r){
		zhuan[l]=ro;return;
	}
	dfs(ro<<1,l,(l+r)/2);
	dfs(ro*2+1,(l+r)/2+1,r);
}
vector<int>g[N<<3],w[N<<3];
void build(int ro,int l,int r,int s,int L,int R,int co){
	if(L<=l&&r<=R){
		g[zhuan[s]].push_back(ro+N*4);
		w[zhuan[s]].push_back(co);
		cout<<s<<' '<<ro+N*4<<' '<<co<<endl;
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid){
		build(ro<<1,l,mid,s,L,R,co);
	}
	if(R>mid){
		build((ro<<1)+1,mid+1,r,s,L,R,co);
	}
}
void build2(int ro,int l,int r,int L,int R,int t,int co){
	if(L<=l&&r<=R){
		g[ro].push_back(zhuan[t]+N*4);
		w[ro].push_back(co);
		cout<<ro<<' '<<t+N*4<<' '<<co<<endl;
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid){
		build(r<<1,l,mid,L,R,t,co);
	}
	if(R>mid){
		build((r<<1)+1,mid+1,r,L,R,t,co);
	}
}
int dis[N<<3];
bool vis[N<<3];
struct node{
	int id,w;
	friend bool operator<(node a,node b){
		return a.w>b.w;
	}
};
priority_queue<node>q;
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	s=zhuan[s];
	node tmp;
	dis[s]=0;
	tmp.id=s;tmp.w=0;
	q.push(tmp);
	while(!q.empty()){
		tmp=q.top();
		q.pop();
		if(vis[tmp.id])continue;
		vis[tmp.id]=1;
	  cout<<tmp.id<<endl;
		int u=tmp.id;
		if(u<=N*4){
			for(int i=0;i<g[u].size();i++){
				int v=g[u][i];
				if(dis[v]>dis[u]+w[u][i]){
					dis[v]=dis[u]+w[u][i];
					tmp.id=v;tmp.w=dis[v];
					q.push(tmp);
				}
			}
			if(tree[u].l==tree[u].r){
				if(dis[u]<dis[u+N*4])dis[u+N*4]=dis[u];
			}else if(u!=1){
				if(dis[u>>1]>dis[u]){
					dis[u>>1]=dis[u];
					tmp.id=u>>1;
					tmp.w=dis[u];
					q.push(tmp);
				}
			}
		}else{
			int u_=u-N*4;
			if(tree2[u_].l==tree2[u_].r){
				if(dis[u_]>dis[u]){
					dis[u_]=dis[u];
					tmp.id=u_;
					tmp.w=dis[u];
					q.push(tmp);
				}
			}else if(u_!=1){
				int ls=u_<<1,rs=u_*2+1;
				if(dis[ls+N*4]>dis[u]){
					dis[ls+N*4]=dis[u];
					tmp.id=ls+N*4;
					tmp.w=dis[u];
					q.push(tmp);
				}
				if(dis[rs+N*4]>dis[u]){
					dis[rs+N*4]=dis[u];
					tmp.id=rs+N*4;
					tmp.w=dis[u];
					q.push(tmp);
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	dfs(1,1,n);
	for(int op,l,r,s,t,w,i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>s>>t>>w;
			build(1,1,n,s,t,t,w);
		}else if(op==2){
			cin>>s>>l>>r>>w;
			build(1,1,n,s,l,r,w);
		}else{
			cin>>t>>l>>r>>w;
			build2(1,1,n,l,r,t,w);
		}
	}
	dijkstra();
	for(int i=1;i<=n;i++)cout<<dis[zhuan[i]]<<endl;
	
	return 0;
}