#include <bits/stdc++.h>
using namespace std;

#define RE register
#define INF 2147483647
#define maxn 10010
#define ll long long

struct Edge{
	ll v,next,w;
}edge[500005];

priority_queue<pair<int,int> >q;

ll n,m,s,v[maxn],head[maxn],ans,x,y,z,cnt,d[maxn];

inline void fread(ll &x){
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    } 
    x*=f;
}

inline void add(int u,int v,int w){
	edge[++cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

inline void dij(){
	for(RE int i=1;i<=n;i++)d[i]=INF;
	memset(v,0,sizeof(v));
	d[s]=0;
	q.push(make_pair(0,s));
	while(q.size()){
		int uu=q.top().second;
		q.pop();
		if(v[uu])continue;
		v[uu]=1;
		for(RE int i=head[uu];i;i=edge[i].next){
			int p=edge[i].v;
			int wi=edge[i].w;
			if(d[uu]>d[p]+wi){
				d[uu]=d[p]+wi;
				q.push(make_pair(-d[p],p));
			}
		}
	} 
}

int main(){
	fread(n);
	fread(m);
	fread(s);
	for(RE int i=1;i<=m;i++){
		fread(x);
		fread(y);
		fread(z);
		add(x,y,z); 
	}
	dij();
	for(RE int i=1;i<=n;i++){
		printf("%d ",d[i]);
	}
	return 0;
}