#include<bits/stdc++.h>
using namespace std;
int n,m,s,x,y,w,d[5005],f[5005][5005];
bool b[5005];
int main() {
	cin>>n>>m>>s;
	for(int i=1; i<=m; i++) {
		cin>>x>>y>>w;
		f[x][y]=w;
		f[y][x]=w;
	}
	//memset(d,0x3f3f3f3f,sizeof(d));
	for(int i=1;i<=n;i++)
	{
		d[i]=INT_MAX;
	}
	for(int i=1; i<=n; i++) {
		d[i]=f[s][i];
	}
	d[s]=0;
	memset(b,false,sizeof(b));
	b[s]=true;
	for(int i=1; i<n; i++) {
		int mind=INT_MAX,k=0;
		for(int j=1; j<=n; j++) {
			if((!b[j])&&(d[j]<mind)) {
				mind=d[j];
				k=j;
			}
		}
		if(k==0)	break;
		b[k]=true;
		for(int j=1; j<=n; j++) {
			if(d[k]+f[k][j]<d[j]) {
				d[j]=d[k]+f[k][j];
			}
		}
	}
	for(int i=1; i<=n; i++) {
		if(d[i]==INT_MAX)
		{
			cout<<2147483647<<" ";
			continue;
		}
		cout<<d[i]<<" ";
	}
	return 0;
}