//单源最短路——Dijsktra算法
#include<bits/stdc++.h>
using namespace std;
//边的结构体
struct Edge{
	int v,e;
	struct Edge* next;
};
const int N=1e5+9;
char flag[N];								//标识数组
int l[N];									//长度数组
//自定义的结构体排序
struct rule{
	bool operator()(const int& a,const int& b){
		return l[a]>l[b];
	}
};
int main(){
	//freopen("d:\\luogu\\P4779test1.txt","r",stdin);
	memset(l,0x3f,sizeof(l));					//长度数组及标识数组的初始化
	memset(flag,false,sizeof(flag));			
	int n,m,s,k,count=0;
	cin>>n>>m>>s;									//输入
	vector<Edge*> v(n+9,NULL);						//邻接表的存储数组
	priority_queue<int,vector<int>,rule> q;										//优先队列
	l[s]=0;
	q.push(s);
	for(int i=0;i<m;i++){
		int v1,v2,e;
		cin>>v1>>v2>>e;
		if(!v[v1]){									//用邻接表存储及其初始化
			v[v1]=new Edge;
			v[v1]->v=v2;
			v[v1]->e=e;
			v[v1]->next=NULL;
		}
		else{
			Edge* p=new Edge;
			p->v=v2;
			p->e=e;
			p->next=v[v1]->next;
			v[v1]->next=p;
		}
	}
	/*for(int i=1;i<=n;i++){
		Edge* p=v[i];
		while(p){
			cout<<i<<"->"<<p->v<<' '<<p->e<<endl;
			p=p->next;
		}
	}*/
	while(1){									//Dijsktra算法的核心
		int k=q.top();
		//cout<<"k = "<<k<<endl;
		if(flag[k]){
			q.pop();
			continue;
		}
		Edge* p=v[k];
		while(p){
			if(flag[p->v]==false){
				l[p->v]=min(l[k]+p->e,l[p->v]);							//更新长度数组
				q.push(p->v);
			}
			p=p->next;
		}
		flag[k]=true;
		q.pop();
		count++;
		//cout<<"count = "<<count<<endl;
		if(count==n)
			break;
	}
	for(int i=1;i<=n;i++){
		cout<<l[i]<<' ';							//输出
	}
	return 0;
}