#include <bits/stdc++.h>
using namespace std;
int n,m,s;
int a,b,c,d;
const int N=3e6+5;
int head[N],ecnt;
struct edge{
	int v,nxt,w;	
}e[N];
void add(int u,int v,int w){
	e[ecnt].v=v;
	e[ecnt].w=w;
	e[ecnt].nxt=head[u];
	head[u]=ecnt++;
}

int lc[N],rc[N];
int cnt;
int rt,rt2;
void build(int &p,int l,int r){
	if(l==r){
		p=l;
		return ;
	}
	p=++cnt;
	int m=l+r>>1;
	build(lc[p],l,m);
	build(rc[p],m+1,r);
	add(p,lc[p],0); add(p,rc[p],0);
} 
void build2(int &p,int l,int r){
	if(l==r){
		p=l;
		return ;
	}
	p=++cnt;
	int m=l+r>>1;
	build2(lc[p],l,m);
	build2(rc[p],m+1,r);
	add(lc[p],p,0); add(rc[p],p,0);
}

void upd(int p,int l,int r,int q,int L,int R,int op){
	if(L<=l&&r<=R){
		if(op==1) add(p,q,0);
		else add(q,p,0);
		return ;
	}
	int m=l+r>>1;
	if(L<=m) upd(lc[p],l,m,q,L,R,op);
	if(R>=m+1) upd(rc[p],m+1,r,q,L,R,op);
}
void add_edge(int a,int b,int c,int d){
	int q=++cnt,q2=++cnt;
	upd(rt,1,n,q,a,b,1);
	upd(rt2,1,n,q2,c,d,2);
	add(q,q2,1);
}

int dis[N];
void spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i+1;i=e[i].nxt){
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w){
				dis[v]=dis[u]+e[i].w;
				q.push(v);
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	memset(head,-1,sizeof(head));
	cnt=n;
	build(rt,1,n); build2(rt2,1,n);
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c>>d;
		add_edge(a,b,c,d);
		add_edge(c,d,a,b);
	} 
	spfa(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<endl;
	}
}