#include<bits/stdc++.h>
using namespace std;
const int INF=0x7ffffff/2;
const int maxx=50005;
int d[maxx];
int vis[maxx];
int g[maxx][maxx],m,n,s;
void Read() {
	int i,x,y,w;
	cin>>n>>m>>s;
	for(i=1; i<=m; i++) {
		cin>>x>>y>>w;
		g[x][y]=w;
	}
}
void di(int v) {
	int i,j,k,minn;
	memset(vis,0,sizeof(vis));
	for(i=1; i<=n; i++) d[i]=INF;
	d[v]=0;
	for(int i=1; i<=n; i++) {
		minn=INF;
		for(j=1; j<=n; j++)
			if(!vis[j]&&minn>d[j]) {
				minn=d[j];
				k=j;
			}
		vis[k]=1;
		for(j=1; j<=n; j++)
			if(g[k][j]>0&&!vis[j]&&d[k]+g[k][j]<d[j]) {
				d[j]=d[k]+g[k][j];
			}
	}
	return ;
}
void Print(){
	for(int i=1;i<=n;i++) cout<<d[i]<<" ";
	return ;
}
int main() {
	Read();
	di(s);
	Print();
	return 0;
}