#include<bits/stdc++.h>
using namespace std;
int n,m,ss,s[100005];
bool vis[100005];
struct node{
	int num,t;
};
vector<node> a[100005];
struct compare{
	bool operator()(int x,int y){
	    return s[x]>s[y];
    }
};
priority_queue<int,vector<int>,compare> q;
void d(){
	int i,p;
	q.push(ss);
	while(!q.empty()){
		p=q.top();
		q.pop();
		if(vis[p]) continue;
		vis[p]=1; 
		for(i=1;i<=a[p][0].num;i++){
			if(s[a[p][i].num]>s[p]+a[p][i].t){
				s[a[p][i].num]=s[p]+a[p][i].t;
				if(!vis[a[p][i].num]) q.push(a[p][i].num);
			}
		}
	}
}
int main(){
	cin>>n>>m>>ss;
	int i,j,k,v;
	node f;
	f.num=0;
	f.t=0;
	for(i=1;i<=n;i++){
		a[i].push_back(f);
		s[i]=0x7fffffff;
	}
	for(i=1;i<=m;i++){
		cin>>j>>k>>v;
		f.t=v;
		f.num=k;
		a[j][0].num++;
		a[j].push_back(f);
	} 
	s[ss]=0;
	d();
	for(i=1;i<=n;i++) cout<<s[i]<<" ";
	return 0;
}