#include <iostream>
using namespace std;
int dis[10005][10005];
int n,m,s;
inline int min_(int a,int b){return a<b?a:b;}
int main(){
	cin>>n>>m>>s;
	for(register int i=1;i<=n;++i)
		for(register int j=i+1;j<=n;++j)
			dis[i][j]=dis[j][i]=2147483647;
	
	register int x,y,z;
	for(register int i=1;i<=m;++i){
		cin>>x>>y>>z;
		dis[x][y]=min_(dis[x][y],z);
	}
	
	for(register int k=1;k<=n;++k){
		for(register int i=1;i<=n;++i){
			if(i==k || dis[i][k]==2147483647)continue;
			for(register int j=1;j<=n;++j){
				dis[i][j]=min_(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	dis[s][s]=0;
	for(register int i=1;i<=n;++i)cout<<dis[s][i]<<" ";
	return 0;
}