#include<cstdio>
#include<queue>
using namespace std;
const int N=2e5+10; 
int n,m,s;
long long ans[N];
int vis[N],head[N],cnt; 
struct edge{
	int to,next,dis;//to:儿子 next:兄弟 dis：权值 
}kun[N];
struct node{
	int ans,id;//ans值  点的编号 
	bool operator <(const node &x)const
	{
		return x.ans<ans;
	}//要背 重载运算符 
};
void add(int u,int v,int d){//起点 终点 权值 
	cnt++;
	kun[cnt].next=head[u];//确定兄弟 
	kun[cnt].to=v;//终点 
	kun[cnt].dis=d; //权值 
	head[u]=cnt; //更新 
} //存图 
priority_queue<node> q; //堆
void Dijstra(){
	ans[s]=0;
	q.push( (node) {0,s});//node为强转 
	for(int i=0;i<N;i++) ans[i]=1e9;//初始化 
	while(!q.empty()){
		node hp=q.top();
		q.pop();
		int idn=hp.id,ansn=hp.ans;
		if(vis[idn]==0){//如果未访问过 
			vis[idn]=1;//标记 
			for(int i=head[idn];i!=0;i=kun[i].next){//枚举 
				int ypy=kun[i].to;
				if(ans[idn]+kun[i].dis<ans[ypy]){//松弛操作 
					ans[ypy]=ans[idn]+kun[i].dis;
					if(vis[ypy]==0){
						q.push( (node){ans[ypy],ypy});
					}
				}
			}
		}
	}
} 
int main(){
	scanf("%d %d %d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		add(a,b,c);
	}
	Dijstra();
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}