#include<iostream>
#include<queue>
using namespace std;
struct node{
	long long to,distance,next;
};
node edge[5*100001];int dis[100001];
int head[100001],flag[100001],visited[100001];
int number,step,maxn,maxm,from,to,distances;
void add(int from,int to,int distance){
	number++;
	edge[number].to=to;
	edge[number].distance=distance;
	edge[number].next=head[from];
	head[from]=number;
};
priority_queue<pair<int,int>>queue_list;
int main(){
	basic_ios<char>::sync_with_stdio(false);
	cin>>maxn>>maxm>>step;
	for(int count=1;count<=maxm;count++){
		cin>>from>>to>>distances;
		add(from,to,distances);
	};
	for(int count=1;count<=maxn;count++){
		dis[count]=2147483647;
	};
	dis[step]=0;
	queue_list.push(make_pair(0,step));
	while(!queue_list.empty()){
		int temp=queue_list.top().second;
		queue_list.pop();
		if(visited[temp]){
			continue;
		};
		visited[temp]=1; 
		for(int count=head[temp];count;count=edge[count].next){
			int went=edge[temp].to;
			long long distanced=edge[temp].distance;
			if(dis[went]>dis[temp]+distanced){
				dis[went]=dis[temp]+distanced;
				queue_list.push(make_pair(-dis[went],went));
			};
		};
	};
	for(int count=1;count<=maxn;count++){
		cout<<dis[count]<<" ";
	};
	return 0;
};