#include<bits/stdc++.h>
using namespace std;
struct edge{
	int to;//所指向的节点 
	int last;//出发节点的上一条边 
	int n;//长度 
}cs[500001];
struct cmp{
	bool operator()(edge a,edge b){
        return a.n<b.n;
    }  
};
priority_queue<edge,vector<edge>,cmp> q;
long long first[50001];
void cnt(int x,int y,int n,int i){//链式前向星读入边 
	edge c;
	c.to=y;
	c.last=first[x];
	first[x]=i;
	c.n=n; 
	cs[i]=c;
	return;
}
long long dis[500001],book[500001];
long long n,m,s;
int main(){
	cin >> n >> m >> s;
	for(int i=1;i<=n;i++)dis[i]=INT_MAX;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		cnt(u,v,w,i); 
	}
	edge q1,q2;
	q1.last=0;
	q1.n=0;
	q1.to=s;
	q.push(q1);
	dis[s]=0;
	while(!q.empty()){
		edge q1,q2;
		q1=q.top();q.pop();
	//	cout << q1.to << " " << q1.n << " " << q1.last << endl;
		if(book[q1.to]!=0){
			continue;
		}
		book[q1.to]=1;
		for(int i=first[q1.to];i!=0;i=cs[i].last){
			//cout <<i << " " << dis[cs[ i ].to ] << " " << cs[ i ].n<< " " << dis[q1.to] << " ";
			dis[cs[ i ].to ] = min(cs[ i ].n+dis[q1.to] , dis[cs[ i ].to ]);
			q2.to=cs[ i ].to;
			q2.n =dis[cs[i].to ];
			q.push(q2);
		//	cout <<  cs[ i ].to << " " <<dis[cs[ i ].to ] <<endl;
		}
	}
	for(int i=1;i<=n;i++){
		cout << dis[i] << " ";
	}
    return 0;
}