#include<bits/stdc++.h>
using namespace std;
int n;

vector<int>dij(vector<vector<int>>m,int root){
	//distance[i]原点到i的距离 
	vector<int>dis(n+1,50005);
	//是否访问过 
	vector<int>visit(n+1,false);
	dis[root] = 0;
	//i遍历所有点(最后一个点不用) 
	for(int i = 1;i<n;i++){
		//node用来寻找当前相邻节点的最近点 
		int node = -1;
		for(int j = 1;j<=n;j++){
			//如果找到 
			if(visit[j]==false&&(node==-1||dis[node]>dis[j])){
				node = j;
			}
		}
		//更新Node相邻点的距离
		for(int j = 1;j<=n;j++){
			dis[j] = min(dis[j],dis[node]+m[node][j]);
		} 
		visit[node] = true;
	}
	return dis;
}

int main(){
	//邻接矩阵初始化 
	int m,s;
	cin>>n>>m>>s;
	vector<vector<int>>mp(n+1,vector<int>(n+1,50005));
	for(int i = 0;i<m;i++){
		int u,v;
		cin>>u>>v;
		cin>>mp[u][v];
	}
	vector<int>ans = dij(mp,s);
	//遍历输出 
	for(int i = 1;i<=n;i++){
		if(ans[i]!=50005)cout<<ans[i]<<endl;
		else cout<<INT_MAX;
	}
	return 0;
}