#include<bits/stdc++.h>
#define INT_MIN -2147483647
#define INT_MAX 2147483647
struct ikun{
	int ed,next,v;
}b[5010];
using namespace std;
int main(){
	int g=0;
	int n,m,s,nbs[1010]={},d[1010]={};
	bool p[1010]={};
	cin>>n>>m>>s;
	for(int i=0;i<=n;i++)
	d[i]=INT_MAX;
	d[s]=0;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		g++;b[g].v=z;b[g].ed=y;b[g].next=nbs[x];nbs[x]=g;
		//g++;b[g].v=z;b[g].ed=x;b[g].next=nbs[y];nbs[y]=g;
	}
	for(int i=1;i<=n;i++){
		int k=0;
		for(int j=1;j<=n;j++)
		if(!p[j]&&d[j]<d[k])k=j;
		int x=nbs[k];
		while(x){
			if(!p[b[x].ed]&&d[b[x].ed]>d[k]+b[x].v)
			d[b[x].ed]=d[k]+b[x].v;
			x=b[x].next;
		}
		p[k]=1;
	}
	for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	return 0;
}