#include <iostream>
#include <cstdio>
using namespace std;
const int Inf = 1e9;
int e[10005][10005],dis[10005],book[10005];
int n,m,Start;

void initE(){
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(i == j){
				e[i][j] = 0;
			}else{
				e[i][j] = Inf; 
			}
		}
	}
	return ;
}

void readLine(){
	for(int i = 1; i <= m; ++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[u][v] = w;
	}
	return ;
}

void initDis(){
	for(int i = 1; i <= n; ++i){
		dis[i] = e[Start][i];
	}
	return ;
}

void initBook(){
	for(int i = 1; i <= n; ++i){
		book[i] = 0;
	}
	book[Start] = 1;
	return ;
}

void Dijskstra(){
	for(int i = 1; i <= n - 1; ++i){
		int minn = Inf,point = 0;
		for(int j = 1; j <= n; ++j){
			if(book[j] == 0 && dis[j] < minn){
				minn = dis[j];
				point = j;
			}
		}
		book[point] = 1;
		for(int j = 1; j <= n; ++j){
			if(e[point][j] < Inf){
				if(dis[j] > dis[point] + e[point][j]){
					dis[j] = dis[point] + e[point][j];
				}
			}
		}
	}
	return ;
}

void print(){
	for(int i = 1; i <= n; ++i){
		printf("%d ",dis[i]);
	}
	return ;
}

int main(){
    scanf("%d%d%d",&n,&m,&Start);
    initE() , readLine() , initDis() , initBook() , Dijskstra() , print();
	return 0;
}

码风可能不太适应，见谅