//计算（目前）到S的距离 //选出一个最短的 //更新其他点到S的距离，为原有最短路径和中转所经过新确定的点再到两者的较小值

include

include

include

using namespace std;

struct edge{

int to;
int value;

}; vector map[1001];

int dis[1001]; bool vis[1001];

int main(){

int n,m,s,from,to,value;
cin>>n>>m>>s;
for(int i=0;i<m;i++){
	cin>>from>>to>>value;
	map[from].push_back(edge{to,value});
}
memset(dis,0x3f,sizeof dis);
vis[s]=true;
for(edge e: map[s]){   //初始化可以直接到达那些点
	dis[e.to]=min(dis[e.to],e.value);
}
for(int i=0;i<n-1;i++){
	int minpoint=s;
	for(int j=1;j<=n;j++){
		if(dis[j]<dis[minpoint]&&!vis[j]){
			minpoint=j;
		}
	}
	vis[minpoint]=true;
	for(edge e: map[minpoint]){  //其他点经过此点
		if(!vis[e.to]){
			dis[e.to]=min(dis[e.to],dis[minpoint]+e.value);
		}
	}
	
}
dis[s]=0;
for(int i=1;i<=m;i++){
	if(dis[i]>10000){
		dis[i]=-1;
	}
}
for(int i=1;i<=n;i++){
	cout<<dis[i]<<" ";
}
return 0;

}