#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> kk;
priority_queue<kk,vector<kk>,greater<kk> > q;
int head[100005],to[200005],ne[200005],W[200005],n,m,s,idx;
int d[100005],b[100005];
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(u==v) continue;
		ne[++idx]=head[u];
		head[u]=idx;
		to[idx]=v;
		W[idx]=w;
	}
	memset(d,0x3f,sizeof d);
	q.push({0,s});
	d[s]=0;
	while(!q.empty()){
		kk l=q.top();
		q.pop();
		if(b[l.second]==1) continue;
		b[l.second]==1;
		for(int i=head[l.second];i;i=ne[i]){
			if(d[to[i]]>l.first+W[i]){
				d[to[i]]=l.first+W[i];
				q.push({d[to[i]],to[i]});
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",d[i]);
	}
}