#include<iostream>
using namespace std;
int head[100000],cnt;
long long dist[1000000];
bool vis[1000000];
int m,n,s;
struct edge{
	int to;
	int nextt;
	int wei;
}edge[1000000];
void add(int x,int y,int z){
	edge[++cnt].to=y;
	edge[cnt].wei=z;
	edge[cnt].nextt=head[x];
	head[x]=cnt;
}
int main(){
	cin>>m>>n>>s;
	for(int i=1;i<=n;i++){
		dist[i]=2147483647;
	}
	dist[s]=0;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	int pos=s;
	while(vis[pos]==0){
		long long minn=2147483647;
		vis[pos]=1;
		for(int i=head[pos];i!=0;i=edge[i].nextt){
			if(!vis[edge[i].to]&&dist[edge[i].to]>dist[pos]+edge[i].wei){
				dist[edge[i].to]=dist[pos]+edge[i].wei;
			}
		}
		for(int i=1;i<=m;i++){
			if(dist[i]<minn&&vis[i]==0){
				minn=dist[i];
				pos=i;
			}
		}
	}
	for(int i=1;i<=m;i++){
		cout<<dist[i]<<' ';
	}
}