#include<iostream>
#include<vector>
#include<cstring> 
using namespace std;
const int N = 10005;
const int inf = 0x3f3f3f3f; 
struct edge{
	int v,w,fq;  
};
vector<edge> e[N+1]; //存储图中每条边
int n,m,a,b,c,s;
int dis[N];
int flag; //标记是否进行松弛 
void Bellman_Ford(int x){ //x--起点
	 memset(dis,inf,sizeof(dis));
	 //处理起点
	 dis[x] = 0;
	 //算法核心：
	 for(int i=1;i<=n-1;i++){  //对每条边进行至多n-1轮松弛 
	 	 flag = 0; 
	 	//遍历每条边(两点确定一条边)
		for(int u=1;u<=n;u++){
			for(int j=0;j<e[u].size();j++){ //遍历起点u的出边 
				int v=e[u][j].v, w = e[u][j].w;  
				if(dis[u] + w < dis[v]){ //松弛操作 
					dis[v] = dis[u]+w;
					flag = 1;
				} 
			} 
		}  
		if(flag == 0) return; 
	 } 
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		e[a].push_back((edge){b,c,a});
	} 
	Bellman_Ford(s);
	for(int i=1;i<=n;i++){
		if(dis[i] == inf) cout<<2147483647<<" ";  //无法到达的点 
		else cout<<dis[i]<<" ";
	}
}