#include<bits/stdc++.h>
#define MAXD 1e6
const int MAXN=10005;
using namespace std;
long long n,m,s,x,y,z,dv,a[MAXN][MAXN],fa[MAXN];
bool visit[MAXN];
long long ans[MAXN],v;
void dj(){
	for(int i=1;i<=n;i++)
		ans[i]=MAXD;
	ans[s]=0;
	memset(visit,false,sizeof(visit));
	visit[s]=true;
	for(int i=1;i<=n;i++){
		v=0;
		dv=MAXD;
		for(int j=1;j<=n;j++)
			if(visit[j]==true && ans[j]<dv){
				v=j;
				dv=ans[j];
			}
		if(v==0) break;
		visit[v]=true;
		for(int j=1;j<=n;j++)
			if(visit[j]==false && ans[v]+a[v][j]<ans[j]){
				ans[j]=ans[v]+a[v][j];
				fa[j]=v;
			}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=MAXD;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		a[x][y]=min(a[x][y],z);
	}
	dj();
	for(int i=1;i<=n;i++)	
		cout<<ans[i]<<" ";
	return 0;
}