#include<bits/stdc++.h>
using namespace std;
const long long M=1e5+20,N=1e4+10,INF=(1<<31)-1;
struct node {
	long long to,nxt,w;
}edge[M];
long long head[N],tot,dix[M],vis[M];
long long n,m,s;
void add(long long u,long long v,long long w) {
	edge[tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].w=w;
	head[u]=tot++;
}
void dist() {
	memset(dix,INF,sizeof(dix));
	memset(vis,0,sizeof(vis));
	dix[s]=0;
	for(long long i=1; i<=n; i++) {
		long long u=0;//min
		for(long long j=1; j<=n; j++) {
			if(!vis[j]&&(u==0||dix[j]<dix[u]))u=j;
		}
		vis[u]=1;
		for(long long j=head[u]; j!=0; j=edge[j].nxt) {
			long long v=edge[j].to,w=edge[j].w;
			dix[v]=min(dix[v],dix[u]+w);
		}
	}
}
int main() {

	long long u,v,w;
	cin>>n>>m>>s;
	for(long long i=1; i<=m; i++) {
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dist();
	for(long long i=1; i<=n; i++) {
		cout<<dix[i]<<" ";
	}
	return 0;
}