#include <bits/stdc++.h>
using namespace std;

const int N=1050;

int n,m,s,l,r,w,a[N][N],ans[N],z[N];

bool p[N][N];

void dfs(int x,int res){
	ans[x]=min(ans[x],res);
	for(int i=1;i<=n;i++){
		if(a[x][i]>0&&p[x][i]==false){
			p[x][i]=true;
			dfs(i,res+a[x][i]);
			p[x][i]=false;
		}
	}
	return;
}

int main(){
	cin>>n>>m>>s;
	memset(ans,1000000,sizeof(ans));
	for(int i=1;i<=m;i++){
		cin>>l>>r>>w;
		a[l][r]==w;
	}
	dfs(s,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}