#include<bits/stdc++.h>
using namespace std;
int n,m,s,dis[100007],cnt=0,head[100007],vis[100007];
struct node{
	int z,next,dis;
};
struct node a[200007];
void add(int j,int k,int l){
	cnt++;
	a[cnt].dis=l;
	a[cnt].z=k;
	a[cnt].next=head[j];
	head[j]=cnt;
}
void di();
struct diss{
	int dis;
    int pos;
    bool operator < ( const diss &x )const
    {
        return x.dis < dis;
    }
};
std::priority_queue<diss> q;
int main(){
	int i,j,k,l;
	cin>>n>>m>>s;
	for(i=0;i<m;i++){
		cin>>j>>k>>l;
		add(j,k,l);
	}
	for(i=1;i<=n;i++){
		dis[i]=9999999;
	}
	di();
	for(i=1;i<=n;i++)
	cout<<dis[i]<<" ";
	return 0;
}
void di(){
	int x,y,k;
	dis[s]=0;
	q.push((diss){dis[s],s});
	while(!q.empty()){
		diss t=q.top();
		q.pop();
		x=t.pos;y=t.dis;
		if(vis[x]==1) continue;
		vis[x]=1;
		k=head[x];//以k为起点的线段 
		while(k!=0){
			if(!vis[a[k].z]&&y+a[k].dis<dis[a[k].z]){
				dis[a[k].z]=y+a[k].dis;
				q.push((diss){dis[a[k].z],a[k].z});
			}
			k=a[k].next;
		}
	}
}