#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
//e邻接矩阵    book标记找到点   dis点之间最短路径 
int e[10001][10001], book[10001],dis[10001],n,m,s,p,q,t;
int inf = 99999999,min_; 
int main(){
	cin >> n >> m >> s;
	//初始邻接矩阵
	for(int i = 1;i <= n;i++) 
		for(int j = 1;j <= n;j++)
			if(i != j)  e[i][j] = inf;
	//输入邻接矩阵
	for(int i = 1;i <= m;i++){
		cin >> p >> q >> t;
		e[p][q] = t;
	} 
	book[s] = 1;   //标记起点
	//初始起点到各个点之间的路径
	for(int i = 1;i <= n;i++)
		dis[i] = e[s][i];   
	int u;   //记录找到点 
	for(int i = 1;i < n;i++){   //遍历n-1个边 
		min_ = inf;
		for(int j = 1;j <= n;j++){   //遍历所有顶点 
			if(book[j] == 0 && dis[j] < min_){  //当前点没有使用，且路径比min_小 
				min_ = dis[j];
				u = j;
			}
		}
		book[u] = 1;  //标记当前点 
		for(int 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(int i = 1;i <= n;i++){
		if(dis[i] >= inf){
			cout << 2147483647 << " ";
			continue;
		} 
		cout << dis[i] << " ";
	}	
	return 0;
}