#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
int n,m,s;
int ans;
int cnt;
bool vis[N];
int head[N];
struct dj{
	int to,dis,next; 
}; 
struct re{
	int dis;
	int pos;
	bool operator <(const re &x)const{
	return x.dis<dis;
	}
};
int dis[N];
dj e[N];
std::priority_queue<re> q;
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
	dis[s]=0;
	for(int i=0;i<m;i++){
		int u,v,d;
		cin>>u>>v>>d;n
		cnt++;
		e[cnt].dis=d;
		e[cnt].to=v;
		e[cnt].next=head[u];
		head[u]=cnt;
	}
	q.push((re){0,s});
	while(!q.empty()){
		re o=q.top();
		q.pop();
		int x=o.pos,d=o.dis;
		if(vis[x]) continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis ) {
			dis[y]=dis[x]+e[i].dis;
			if(!vis[y]){
				q.push((re){dis[y],y});
			}
			}
		}
	}
	for(int i=1;i<=n;i++){
	cout<<dis[i]<<' ';	
	}
}