#include<bits/stdc++.h>
using namespace std;
int main(){
	int e[10001][10001],dis[10001],book[10001],i,j,n,m,t1,t2,t3,u,v,minn,s;
	int inf=99999999;
	cin >> n >> m >> s;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
			else e[i][j]=inf;
		}
	}
	for(i=1;i<=m;i++){
		cin >> t1 >> t2 >> t3;
		e[t1][t2]=t3;
	}
	for(i=1;i<=n;i++) dis[i]=e[1][i];
	for(i=1;i<=n;i++) book[i]=0;
	book[1]=1;
	for(i=s;i<=n-1;i++){
		minn=inf;
		for(j=1;j<=n;j++){
			if(book[j]==0&&dis[j]<minn){
				minn=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(v=1;v<=n;v++){
			if(e[u][v]<inf){
				if(dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v];
			}
		}
	}
	for(i=1;i<=n;i++) cout << dis[i] << " ";
	return 0;
}